Re:Boolean expressions and QC
on
Does P = NP?
·
· Score: 1
Determining whether a boolean formula has a solution (assignment of trues/falses to the variables, that makes the formula evaluate to true) is NP-complete.
Determining if such a formula is a tautology (true) or if it is a contradiction (false) are both coNP-complete problems (conjectured to be harder than NP).
I'm unaware of QC making progress on these problems.
Re: Is this problem NP complete?
on
Does P = NP?
·
· Score: 1
There is a linear-time algorithm for 2SAT. It is basically as hard as finding a path from one node s to another node t in a directed graph.
By the way, 2SAT is NL-complete (nondeterministic logarithmic space complete with respect to logspace reductions), which implies it is in P.
(1) Yes, the problem under consideration in the paper is indeed NP-complete, proven a long time ago by someone other than the author of that paper.
(2) You DO NOT need to show an isomorphism between your problem and an NP-complete problem to show your problem is NP-complete.
You give a polynomial time reduction from the particular NP-complete problem to your candidate problem. Think of it as showing that the NP-complete problem is a "special case" of the candidate problem (that's roughly what goes on, but not exactly).
And a reduction need not be an isomorphism. The isomorphism bit is a totally different issue which people know little about. The known NP-complete problems are indeed isomorphic, but it is not for certain that all of the complete problems are.
If you mean "many-one polynomial time equivalence", that is A = B iff A is many-one polytime reducible to B, and B is many-one polytime reducible to A, then your statement follows directly from the definition of NP-completeness. I think this is probably what you mean, judging by the context.
If you mean "polynomial time isomorphic", this is not known. (It was conjectured in the '70s, but hasn't been proven. Many think this is not true.)
> there are going to be a great many people upset > and offended at the creation of thought crimes
The creation of "thought crimes" is an issue that is currently under heavy debate, but I'm not talking about the Internet.
They are more familiarly known as "hate crimes." People want to give extra punishment because a particular thought/emotion/attitude towards another group motivated the crime. Hot words like racism, homophobia, anti-Semitism, etc. are examples of some of the thoughts.
And believe it or not, some groups actually want these hate crime laws.
But the theory of computation still applies... there are some problems that will always be unsolvable via a computer, even if one can go arbitrarily far back in time arbitrarily many times. Whatever fancy computer you come up with, if it is a universal one (one that can emulate any other computer of its kind), I can just feed that same computer its own encoding, and some string, and no one (i.e. no computer) will be able to tell if that computer will ever stop running. In finite time.
Slashdot Mirror
Determining whether a boolean formula has a solution (assignment of trues/falses to the variables, that makes the formula evaluate to true) is NP-complete.
Determining if such a formula is a tautology (true) or if it is a contradiction (false) are both coNP-complete problems (conjectured to be harder than NP).
I'm unaware of QC making progress on these problems.
There is a linear-time algorithm for 2SAT. It is basically as hard as finding a path from one node s to another node t in a directed graph.
By the way, 2SAT is NL-complete (nondeterministic logarithmic space complete with respect to logspace reductions), which implies it is in P.
(1) Yes, the problem under consideration in the paper is indeed NP-complete, proven a long time ago by someone other than the author of that paper.
(2) You DO NOT need to show an isomorphism between your problem and an NP-complete problem to show your problem is NP-complete.
You give a polynomial time reduction from the particular NP-complete problem to your candidate problem. Think of it as showing that the NP-complete problem is a "special case" of the candidate problem (that's roughly what goes on, but not exactly).
And a reduction need not be an isomorphism. The isomorphism bit is a totally different issue which people know little about. The known NP-complete problems are indeed isomorphic, but it is not for certain that all of the complete problems are.
Equivalent in what sense?
If you mean "many-one polynomial time equivalence", that is A = B iff A is many-one polytime reducible to B, and B is many-one polytime reducible to A, then your statement follows directly from the definition of NP-completeness. I think this is probably what you mean, judging by the context.
If you mean "polynomial time isomorphic", this is not known. (It was conjectured in the '70s, but hasn't been proven. Many think this is not true.)
> there are going to be a great many people upset
> and offended at the creation of thought crimes
The creation of "thought crimes" is an issue that is currently under heavy debate, but I'm not talking about the Internet.
They are more familiarly known as "hate crimes." People want to give extra punishment because a particular thought/emotion/attitude towards another group motivated the crime. Hot words like racism, homophobia, anti-Semitism, etc. are examples of some of the thoughts.
And believe it or not, some groups actually want these hate crime laws.
But the theory of computation still applies... there are some problems that will always be unsolvable via a computer, even if one can go arbitrarily far back in time arbitrarily many times. Whatever fancy computer you come up with, if it is a universal one (one that can emulate any other computer of its kind), I can just feed that same computer its own encoding, and some string, and no one (i.e. no computer) will be able to tell if that computer will ever stop running. In finite time.