# Questions tagged [np]

NP stands for Nondeterministic Polynomial time.

112 questions
Filter by
Sorted by
Tagged with
45 views

116 views

### List of NP-Complete graph problems/ properties?

Is there a good source to find various decision problems on graph and networks? For a project I'm doing it'd be useful to be able to look at lots of different problems. Is there a good source for ...
122 views

### Understanding non-equivalence of proof lengths according to proof systems

Here, in section 4.3, Fortnow says: But to prove P != NP we would need to show that tautologies cannot have short proofs in an arbitrary proof system. I am ...
102 views

### Fagin's Theorem implications

I was going through Fagin's Theorem (summary on wiki) and if I understood correctly Existential Second Order Logic (ESO) can be used to represent any NP problem, the same can be said for a Non-...
142 views

### Is the following problem in $coNP$?

Given an $n\times n$ matrix $M$ with $\mathbb Z$ entries is 'does an $\frac n2\times\frac n2$ minor of $M$ vanish?' in $\bf{coNP}$? At least one $\frac n2\times\frac n2$ minor non-vanish implies rank ...
93 views

### Are there any known languages in the intersection of NP and co-NP but not in P? [closed]

We currently don't know the relationship between NP and co-NP, but would it be possible to show whether the intersection is equal to P? I can't think of any languages in both NP and co-NP, but not in ...
232 views

### Complexity of a problem over acyclic context-free grammars

Let $G$ be an acyclic, context-free grammar over a fixed alphabet $\Sigma=\{a_1,\dots,a_k\}$ with the restriction (without loss of generality) that $|w|=2$ for each rule $A\to w$ in the grammar. ...
246 views

### Have people looked for parameterized algorithms for problems that are not in NP?

Are there problems that are not in NP (e.g., NEXP-complete problems) but admit FPT algorithms for a reasonable parameterization (and specifically, the standard parameterization of a problem -- the ...
337 views

### “Berman-Hartmanis Conjecture Separates NP From All Super-Poly. DTIME Classes” — Worthy of arXiv.org?

Do you believe this paper is worthy of arXiv.org? I have searched via Google, and to my knowledge, no one else has this result. I'm not asking you to fully scrutinize the paper, I'm just asking if you ...
2k views

### Algorithm whose running time depends on P vs. NP

Is there a known, explicit example of an algorithm with the property such that if $P\neq NP$ then this algorithm doesn't run in polynomial time and if $P=NP$ then it does run in polynomial time?
447 views

114 views

### NP completeness of classes of spanning trees

I am teaching a complexity course, and I want to give some examples of similar looking problems such that one is in P, and the other is NP complete. This made me think of the following problem: does ...
132 views