bebetoss

Faça um procedimento recursivo determinístico para imprimir, dados dois inteiros positivos n, k todas as combinaçoes possíveis de k elementos contidas no conjunto dos inteiros no intervalo [1,n]. o procedimento deve imprimir uma combinação por linha, sem repetir combinações. sabe-se que dentro de uma combinação n ordem dos elementos não é importante e não é permitida a repetição dos elementos. problema de localização: Entrada: dois inteiros positivos, n e k, comm n>0 saída: a listagem das combinações, conforme o enunciado

Um versão "pi "do problema da mochila é definida da seguinte forma: dada uma mochila M com capacidade W e n objetos a.i distintos, como i pertence a [1,n] existe uma carga com valor maior ou iguala k que a mochila é capaz de carregar?cada objeto a.i tem peso p1 e valor v1 a) apresenta um algoritmo NP que exibe um certificado para o problema pi b)apresente um algoritmo P que reconhece um certificado para o problema pi

Ainda tratando do problema SAT, considere o seguinte: (a) é sabido que 3-SAT está na classe NP-Completo; (b) é fácil provar que k-SAT alfa x-SAT se x=k-1 (c) é facil prvar que 2-SAT está na classe P. Explique porque esses argumentos não são admitidos como prova para P=NP

Seja SAT o problema da satisfabilidade em sua versaode decisao. Esse problema consiste em determinar, dada uma expressao lógica E na forma normal conjuntiva, se existe uma distribuição de valores booleanos para as variáveis que tornem a expressão E válida.Quando o número de variáveis nos blocos(clausulas com "ou) é constante e vale K temos casos particulares do problema SAT que são chamados de K-SAT a) mostre que 2-SAT alfa 3-sat b) mostre 4-sat alfa 3-sat