Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with np
Search options not deleted
user 51868
Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.
6
votes
1
answer
850
views
How does (non)deterministic time relate to verifiability?
So far, from all the research I've done, I've come across 2 different ways that NP time is explained. One is that a nondeterministic turing machine is able to solve the problem in polynomial time. …
- 499
6
votes
1
answer
1k
views
Is EXPTIME "solvable" or "checkable" in exponential time?
It would make sense to me, that if EXP contains problems that are exponentially difficult to check, that they would contain problems that are harder than NP-complete ones. … Wouldn't EXP therefore be a subset of NP (and so would R), as problems that are harder (like R) are still solvable in "non-deterministic" time? …
- 499
3
votes
1
answer
563
views
NP and verifiability equivalence - does this guarantee that any certificate can be verified ...
Intuitively, NP has been described as the class of all problems which a solution certificate can be verified in polynomial time. … Let's say we have a problem $K$ in NP and we have a certificate $c_e$ obtained externally that proves a YES or NO result for $x$. …
- 499
2
votes
1
answer
129
views
Questions on Sipser's NP implying verifiability?
I've revisited trying to understand the proof to why NTM exists iff there is a verifier. I think I'm finally understanding the proof but I want to make sure and thus have some questions as follow up a …
- 499
8
votes
1
answer
4k
views
How do we know for sure that EXPTIME ≠ P?
(Wikipedia) It makes absolute sense intuitively that this is the case, as does P≠NP. … If we assume P=NP and NP=EXP, P=EXP and that contradicts P≠EXP. So one of those statements MUST be false. But we can only conjecture that both these are false, and can't prove it? Is that the case? …
- 499
4
votes
2
answers
1k
views
How are games like chess provably harder than NP?
From this question, I had the debate about how problems harder than NP are proved. … I said that intuitively I understand it as (from this video explaining that some problems are provably harder than NP):
Generalized chess is harder than NP, and is EXPTIME-complete for the
decision problem …
- 499
5
votes
3
answers
1k
views
What complexity class would this version of generalized chess fall?
Therefore it's not in NP.
But if you were to ask the decision problem "Given an nxn board with a given position, can white win?" and apply it to generalized chess, would this variation be in NP? … For this decision problem, would it fall in NP, because a problem solvable by a DTM in EXPTIME and verifiable in polynomial time would be NP-complete, yes? …
- 499