Re: NP completeness

From: Daniel McLaury (daniel_mcl_at_hotmail.com)
Date: 07/28/04 

Date: 27 Jul 2004 19:52:51 -0700

There is no NP-complete problem to which the answer is always "yes."
This is easy to prove; if a problem is NP-complete, it is equivalent to
solving some problem in propositional logic, because all NP-complete
problems are equivalent to each other (this is the definition of
NP-complete). This would mean that a problem to which the answer is
always "yes" could somehow be used to solve problems in propositional
logic. But, of course, a program which always prints out "Yes" gives
you absolutely no information at all.

What do you mean, you *think* you have a polynomial time algorithm to
produce a "yes" ? I mean, the program given by

PRINT "YES"

is not only polynomial time, it's constant time -- it doesn't even look
at its input.

Perhaps you are talking about two different problems here. Upon
re-reading your post, I think perhaps you mean that you have seen a
proof that a solution always *exists*, but to generate it is an
NP-complete problem. Now, if you are saying you have a polynomial
time algorithm that generates the solution to a NP-complete problem, I
(and the rest of the world) would love to see it; this is one of the
biggest unsolved problems in mathematics.

It'd be a lot easier to respond if you at least told me what the
problem you're talking about is, and described your algorithm.

Relevant Pages

  • Re: NP-complete and NP-Hard?
    ... >> polynomial time? ... > An NP-complete problem is a problem that is completely ... Jym. ... Prev by Date: ...
    (comp.theory)
  • If P==NP how to solve the Prime Factorization problem?
    ... I am looking for information on "if a polynomial time algorithm exists ... factorization ends up in P. ... for any other NP-Complete problem. ...
    (comp.theory)
  • Re: P=NP Proof Published at CERN
    ... any NP-complete problem in polynomial time will be ... fame, the Clay prize money, and perhaps even ...
    (sci.math)
  • Re: P = NP, background study?
    ... In response to Casey Hawthorne...it's already been proven that if you ... can solve one NP-complete problem in polynomial time, ... then there would be no NP-complete problem that is not solvable ... Or between discrete mathematics and flagrant mathematics. ...
    (comp.theory)