Return to Answer

Yes, of course you can

For instance:

We have 2-SAT( http://en.wikipedia.org/wiki/2-satisfiability ), that is an problem in P.We we have SAT( http://en.wikipedia.org/wiki/Boolean_satisfiability_problem ) which is an NP-complete problem. We can convert all 2-sat instances to sat instances

If we have a 2-SAT formula like this:

$$ (x_{1} \vee x_{2}) \wedge (\neg x_{3} \vee x_{4}) $$

we can convert it to SAT by inserting a dummy variable in each clause:

$$ (x_{1} \vee x_{2} \vee \neg x_{5}) \wedge (\neg x_{3} \vee x_{4} \vee \neg x_{6}) \wedge x_{5} \wedge x_{6} $$

Yes, of course you can

For instance:

We have 2-SAT( http://en.wikipedia.org/wiki/2-satisfiability ), that is an problem in P. We have CNFSAT( http://en.wikipedia.org/wiki/Boolean_satisfiability_problem ) which is an NP-complete problem. We can convert all 2-sat instances to cnfsat instances

If we have a 2-SAT formula like this:

$$ (x_{1} \vee x_{2}) \wedge (\neg x_{3} \vee x_{4}) $$

we can convert it to CNFSAT by inserting a dummy variable in each clause:

$$ (x_{1} \vee x_{2} \vee \neg x_{5}) \wedge (\neg x_{3} \vee x_{4} \vee \neg x_{6}) \wedge x_{5} \wedge x_{6} $$

Yes, of course you can

For instance:

We have 2-SAT( http://en.wikipedia.org/wiki/2-satisfiability ), that is an problem in P.We we have SAT( http://en.wikipedia.org/wiki/Boolean_satisfiability_problem ) which is an NP-complete problem. We can convert all 2-sat instances to sat instances

If we have a 2-SAT formula like this:

$$ (x_{1} \vee x_{2}) \wedge (\neg x_{3} \vee x_{4}) $$

we can convert it to SAT by inserting a dummy variable in each clause:

$$ (x_{1} \vee x_{2} \vee \neg x_{5}) \wedge (\neg x_{3} \vee x_{4} \vee \neg x_{6}) \wedge x_{5} \wedge x_{6} $$

You can reduce all P problems to NP problems with this method because you can convert all problems in P to 2-SAT problems.

Yes, of course you can

For instance:

We have 2-SAT( http://en.wikipedia.org/wiki/2-satisfiability ), that is an problem in P.We we have SAT( http://en.wikipedia.org/wiki/Boolean_satisfiability_problem ) which is an NP-complete problem. We can convert all 2-sat instances to sat instances

If we have a 2-SAT formula like this:

$$ (x_{1} \vee x_{2}) \wedge (\neg x_{3} \vee x_{4}) $$

we can convert it to SAT by inserting a dummy variable in each clause:

$$ (x_{1} \vee x_{2} \vee \neg x_{5}) \wedge (\neg x_{3} \vee x_{4} \vee \neg x_{6}) \wedge x_{5} \wedge x_{6} $$

Yes, of course you can

For instance:

We have 2-SAT( http://en.wikipedia.org/wiki/2-satisfiability ), that is an problem in P.We we have 3SAT( http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#3-satisfiability ) which is an NP-complete problem. We can convert all 2-sat instances to 3-sat instances

If we have a 2-SAT formula like this:

$$ (x_{1} \vee x_{2}) \wedge (\neg x_{3} \vee x_{4}) $$

we can convert it to 3SAT by inserting a dummy variable in each clause:

$$ (x_{1} \vee x_{2} \vee x_{5}) \wedge (\neg x_{3} \vee x_{4} \vee x_{6}) $$

You can reduce all P problems to NP problems with this method because you can convert all problems in P to 2-SAT problems.

Yes, of course you can

For instance:

We have 2-SAT( http://en.wikipedia.org/wiki/2-satisfiability ), that is an problem in P.We we have SAT( http://en.wikipedia.org/wiki/Boolean_satisfiability_problem ) which is an NP-complete problem. We can convert all 2-sat instances to sat instances

If we have a 2-SAT formula like this:

$$ (x_{1} \vee x_{2}) \wedge (\neg x_{3} \vee x_{4}) $$

we can convert it to SAT by inserting a dummy variable in each clause:

$$ (x_{1} \vee x_{2} \vee \neg x_{5}) \wedge (\neg x_{3} \vee x_{4} \vee \neg x_{6}) \wedge x_{5} \wedge x_{6} $$

You can reduce all P problems to NP problems with this method because you can convert all problems in P to 2-SAT problems.