Hacker News
new
|
past
|
comments
|
ask
|
show
|
jobs
|
submit
login
morsch
on Dec 11, 2012
|
parent
|
context
|
favorite
| on:
Jun Fukuyama's P≠NP Page
Yes, that's what he is saying,
every
CLIQUE algorithm takes at least exponential time.
mdxn
on Dec 11, 2012
|
next
[–]
No, he is claiming that l-CLIQUE requires exponential circuit size (this is the reason that most of the proof talks about circuit complexity and not time bounded Turing Machines). This is not necessarily the same thing as exponential time.
GoGoGalois
on Dec 11, 2012
|
prev
[–]
Oh ok, I thought the first post was referring to a single algorithm, not every possible algorithm. My mistake.
gburt
on Dec 11, 2012
|
parent
[–]
Sorry, if I could I would edit it to be more clear. We definitely need to show that no algorithm can exist with poly runtime for all inputs.
Guidelines
|
FAQ
|
Lists
|
API
|
Security
|
Legal
|
Apply to YC
|
Contact
Search: