4 ms·

Can we get a laymans explanation of what this is about? I understand what p np is, but don't really understand what this person is claiming. Is this some kind o

Can we get a laymans explanation of what this is about? I understand what p np is, but don't really understand what this person is claiming. Is this some kind of claim about the overall concept of p np? Or proving a specific case?

deleted 14y ago
[deleted]
nate_martin 14y ago
I think he is showing the clique problem cannot be solved in polynomial time. Since clique is in NP and not P, P!=NP.
- cgray4 14y ago
  The claim is that since clique is in NP-complete and not P, P != NP. (Every problem in P is in NP.)
notimetorelax 14y ago
If I understand it right he showed that Clique cannot be solved in polynomial time, since any NP complete problem is at least as hard as Clique none of those problems can be solved in polynomial time. So he used Clique to draw general conclusion that P!=NP.
- sjg007 14y ago
  This only works if all NPC problems can be converted to CLIQUE?
  - qdog 14y ago
    All NP problems can be converted into the other NP problems, therefore if you can prove it for one NP problem, you prove it for all NP problems.
    - cgray4 14y ago
      You missed a few words. Any NP-complete problem can be converted into any other NP-complete problem in polynomial time.
      - qdog 14y ago
        Right, oops.
SenorWilson 14y ago
Basically prove/disprove a p-np problem can be solved(in polynomial time) then you've proved it for the rest of the p-np problems.
- emillon 14y ago
  I think that you mean a NP-complete problem. There's no such thing as a "p-np problem".
dbaupp 14y ago
This is a specific case that (maybe) proves the general claim that P != NP. Proving an inequality is "easy", because only requires a single counterexample: if there is one problem in NP that is not in P (I.e. an NP problem not solvable in polynomial time), then NP can't possible equal P. Fukuyama is proposing that CLIQUE is such a counter-example. (Proving the inequality doesn't actually require the special property of NP-completeness which others are talking about; that is only useable in a proof P = NP.)
- chimeracoder 14y ago
  > Proving an inequality is "easy", because only requires a single counterexample: Proving an equality isn't exactly "harder" (no NP-hard pun intended) - all you have to do is show that a single NP-complete problem can be reduced to a problem within P in polynomial time.
  - PeterBB 14y ago
    That's true in this case, but only because we have other results showing that various problems are NP-complete.

deleted 14y ago

[deleted]

nate_martin 14y ago

I think he is showing the clique problem cannot be solved in polynomial time. Since clique is in NP and not P, P!=NP.

cgray4 14y ago
The claim is that since clique is in NP-complete and not P, P != NP. (Every problem in P is in NP.)

notimetorelax 14y ago

If I understand it right he showed that Clique cannot be solved in polynomial time, since any NP complete problem is at least as hard as Clique none of those problems can be solved in polynomial time. So he used Clique to draw general conclusion that P!=NP.

sjg007 14y ago
This only works if all NPC problems can be converted to CLIQUE?
- qdog 14y ago
  All NP problems can be converted into the other NP problems, therefore if you can prove it for one NP problem, you prove it for all NP problems.
  - cgray4 14y ago
    You missed a few words. Any NP-complete problem can be converted into any other NP-complete problem in polynomial time.
    - qdog 14y ago
      Right, oops.

SenorWilson 14y ago

Basically prove/disprove a p-np problem can be solved(in polynomial time) then you've proved it for the rest of the p-np problems.

emillon 14y ago
I think that you mean a NP-complete problem. There's no such thing as a "p-np problem".

dbaupp 14y ago

This is a specific case that (maybe) proves the general claim that P != NP. Proving an inequality is "easy", because only requires a single counterexample: if there is one problem in NP that is not in P (I.e. an NP problem not solvable in polynomial time), then NP can't possible equal P. Fukuyama is proposing that CLIQUE is such a counter-example. (Proving the inequality doesn't actually require the special property of NP-completeness which others are talking about; that is only useable in a proof P = NP.)

chimeracoder 14y ago
> Proving an inequality is "easy", because only requires a single counterexample: Proving an equality isn't exactly "harder" (no NP-hard pun intended) - all you have to do is show that a single NP-complete problem can be reduced to a problem within P in polynomial time.
- PeterBB 14y ago
  That's true in this case, but only because we have other results showing that various problems are NP-complete.