Analise as afirmativas a seguir: I. O problema de satisfatibilidade booleana é o problema de determinar se existe determinada valoração para as var...

Analise as afirmativas a seguir: I. O problema de satisfatibilidade booleana é o problema de determinar se existe determinada valoração para as variáveis de determinada fórmula booleana tal que essa valoração satisfaça essa fórmula em questão. II. O problema SAT é um problema de decisão de classe de complexidade polinomial que consiste em determinar a inexistência de alguma atribuição de valores verdade que satisfaça uma fórmula lógica na forma normal conjuntiva. III. Os problemas em P também podem ser reduzidos a SAT, mas, como já se conhece uma boa solução para problemas P, estes não são considerados parte de NP-completo. IV. O problema 3SAT é um caso especial ou uma variação do problema SAT original. Uma instância de 3SAT é uma expressão booleana em que cada clausula contém pelo menos três variáveis. Considerando o contexto apresentado, verifica-se que:
a afirmativa I é verdadeira. A alternativa I está correta, porque o problema SAT visa a encontrar uma solução verdade para dada fórmula booleana, e, caso encontrada, a fórmula é considerada “satisfatível”. A afirmativa II está incorreta, porque o SAT é um problema de decisão NP-completo que consiste em determinar a existência de alguma atribuição de valores verdade que satisfaça uma fórmula lógica na forma normal conjuntiva. A afirmativa III está correta, pois problemas P podem ser reduzidos usando SAT, mas essa redução se torna desnecessária, pois problemas P são determinísticos e aceitam uma solução polinomial. A afirmativa IV está errada, porque cada cláusula contém exatamente três variáveis.
a afirmativa III é verdadeira. A alternativa I está correta, porque o problema SAT visa a encontrar uma solução verdade para dada fórmula booleana, e, caso encontrada, a fórmula é considerada “satisfatível”. A afirmativa II está incorreta, porque o SAT é um problema de decisão NP-completo que consiste em determinar a existência de alguma atribuição de valores verdade que satisfaça uma fórmula lógica na forma normal conjuntiva. A afirmativa III está correta, pois problemas P podem ser reduzidos usando SAT, mas essa redução se torna desnecessária, pois problemas P são determinísticos e aceitam uma solução polinomial. A afirmativa IV está errada, porque cada cláusula contém exatamente três variáveis.
as afirmativas I e III são verdadeiras. A alternativa I está correta, porque o problema SAT visa a encontrar uma solução verdade para dada fórmula booleana, e, caso encontrada, a fórmula é considerada “satisfatível”. A afirmativa II está incorreta, porque o SAT é um problema de decisão NP-completo que consiste em determinar a existência de alguma atribuição de valores verdade que satisfaça uma fórmula lógica na forma normal conjuntiva. A afirmativa III está correta, pois problemas P podem ser reduzidos usando SAT, mas essa redução se torna desnecessária, pois problemas P são determinísticos e aceitam uma solução polinomial. A afirmativa IV está errada, porque cada cláusula contém exatamente três variáveis.
as afirmativas II, III e IV são verdadeiras. A alternativa I está correta, porque o problema SAT visa a encontrar uma solução verdade para dada fórmula booleana, e, caso encontrada, a fórmula é considerada “satisfatível”. A afirmativa II está incorreta, porque o SAT é um problema de decisão NP-completo que consiste em determinar a existência de alguma atribuição de valores verdade que satisfaça uma fórmula lógica na forma normal conjuntiva. A afirmativa III está correta, pois problemas P podem ser reduzidos usando SAT, mas essa redução se torna desnecessária, pois problemas P são determinísticos e aceitam uma solução polinomial. A afirmativa IV está errada, porque cada cláusula contém exatamente três variáveis.
as afirmativas I, II e III são verdadeiras. A alternativa I está correta, porque o problema SAT visa a encontrar uma solução verdade para dada fórmula booleana, e, caso encontrada, a fórmula é considerada “satisfatível”. A afirmativa II está incorreta, porque o SAT é um problema de decisão NP-completo que consiste em determinar a existência de alguma atribuição de valores verdade que satisfaça uma fórmula lógica na forma normal conjuntiva. A afirmativa III está correta, pois problemas P podem ser reduzidos usando SAT, mas essa redução se torna desnecessária, pois problemas P são determinísticos e aceitam uma solução polinomial. A afirmativa IV está errada, porque cada cláusula contém exatamente três variáveis.