> Are there problems for which we can prove they are in NP but also prove they cannot have polynomial time (P time) solutions?
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.)
Cool, thank you. Yeah that makes sense. I didn't expect you to actually explain the entire thing, I just wondered if you had some, you know, insight. It's all good hahaha! :) I like your cheatsheet, I guess that applies to your previos definition of co-NP ! :)
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.)