Consider the decision Problem 2CFSAT defined as follows:{ φ

.Solvable in constant time since any input instance is satisfiable.

.Solvable in polynomial time by reduction to directed graph reachability.

1.	Consider the decision Problem 2CFSAT defined as follows:{ φ \| φ is a satisfiable propositional formula in CNF with at most two literals per clause }For example, φ = (x1 v x2)⋀ (x1v x3̅ ) ⋀ (x2 v x4) is a Boolean formula and it is in 2 CNFSAT.The decision problem 2 CNFSAT is
A.	.NP complete
B.	.Solvable in polynomial time by reduction to directed graph reachability.
C.	.Solvable in constant time since any input instance is satisfiable.
D.	.NP-hard but not NP-complete
Answer» C. .Solvable in constant time since any input instance is satisfiable.

Discussion

No Comment Found

Related MCQs

Consider the following sets:S1. Set of all recursively enumerable languages over the alphabet {0,1}S2. Set of all syntactically valid C programsS3. Set of all languages over the alphabet {0,1}S4. Set of all non-regular languages over the alphabet {0,1}Which of the above sets are uncountable?
If L ϵ NP is a language such that L' ≤p L for some L' ϵ NPC, then:
Let A and B be finite alphabets and let # be a symbol outside both A and B. Let f be a total function from A* to B*. We say f is computable if there exists a Turing machine M which given an input x in A*. always halts with f(x) on its tape. Let Lf denote the language {x # f(x) |x ∈ A*}. Which of the following statements is true:
If \( L\) and \(\bar L\) are recursively enumerable, then L is
Consider the following languages.L1 = { | M takes at least 2016 steps on some input},L2 = { | M takes at least 2016 steps on all inputs} andL3 = { | M accepts ϵ},Where for each Turing machine M, denotes a specific encoding of M. Which one of the following is TRUE?
Let L1 be regular language, L2 be a deterministic context free language and L3 a recursively enumerable language, but not recursive. Which one of the following statements is false?
Consider the following statements.I. The complement of every Turing decidable language is Turing decidableII. There exists some language which is in NP but is not Turing decidableIII. If L is a language in NP, L is Turing decidableWhich of the above statements is/are true?
Language L1 is polynomial time reducible to language L2. Language L3 is polynomial time reducible to L2, which in turn is polynomial time reducible to language L4. Which of the following is/are true?I. if L4 ∈ P, then L2 ∈ PII. if L1 ∈ P or L3 ∈ P, then L2 ∈ PIII. L1 ∈ P, if and only if L3 ∈ PIV. if L4 ∈ P, then L1 ∈ P and L3 ∈ P
Consider the following two statements about regular languages:S1: Every infinite regular language contains an undecidable language as a subset.S2: Every finite language is regular.Which one of the following choices is correct?
Let G1 and G2 be arbitrary context free languages and R an arbitrary regular language.Consider the following problems:(A) Is L(G1) = L(G2)?(B) Is L(G2) ≤ L(G1)?(C) Is L(G1) = R?Which of the problems are undecidable ?Choose the correct answer from the options given below:

Consider the decision Problem 2CFSAT defined as follows:{ φ | φ is a satisfiable propositional formula in CNF with at most two literals per clause }For example, φ = (x1 v x2)⋀ (x1v x3̅ ) ⋀ (x2 v x4) is a Boolean formula and it is in 2 CNFSAT.The decision problem 2 CNFSAT is

Discussion

No Comment Found

Related MCQs

Reply to Comment