|
|
|
|
|
|
by keepamovin
796 days ago
|
|
|
Thanks for the alt NP definition. I'd be fine to talk to people we just have to clarify the definitions first. Haha! :) I think mine's good but I get if you differ, no worries. It's actually a very fascinating definition and question: Are there problems for which we can prove they are in NP but also prove they cannot have polynomial time (P time) solutions? I did check out that wiki page first, but found it super difficult to parse. Do you have some insight that could help me understand more simply/intuitively?? For instance, I found the definition of NP as P if you have an NFA, to be super easy to understand. But when that wiki starts talking about "certificates" I just have no idea. That is, co-NP is the set of decision problems where there exists a polynomial
{\displaystyle p(n)} and a polynomial-time bounded Turing machine M such that for every instance x, x is a no-instance if and only if: for some possible certificate c of length bounded by {\displaystyle p(n)}, the Turing machine M accepts the pair (x, c). |
|
|
That's exactly the famous P!=NP question.
> I did check out that wiki page first, but found it super difficult to parse. Do you have some insight that could help me understand more simply/intuitively??
Scott Aaronson might have some good intro material on his blog. Otherwise, you can just ask your favourite search engine (or AI bot) for some intro material.
> For instance, I found the definition of NP as P if you have an NFA, to be super easy to understand. But when that wiki starts talking about "certificates" I just have no idea.
The certificate is the 'cheatsheet' or 'hint'. Basically the question is, how well can you do in an exam where you have to show your work, if someone gives you all the answers? (But that guy is a troll, so you can't trust him, and still need to verify everything.)