Questions tagged [np]
Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.
96 questions with no upvoted or accepted answers
9
votes
0
answers
362
views
Are there consequences for P ≠ NP that are unintuitive?
It's often regarded that the most intuitive answer to the question of $P$ vs $NP$ is that $P ≠ NP$. This is often illustrated with some consequences that would follow if $P = NP$ were true. Things ...
- 525
5
votes
0
answers
286
views
If BQP is contained in any level of the Polynomial Hierarchy, does it then follow that $NP \subseteq BQP$ implies $PH \subseteq BQP$?
I think this is implied in this paper by Aaronson (http://www.scottaaronson.com/papers/bqpph.pdf) but I am not sure.
Begin with $NP \subseteq BQP$ (*)
$\Sigma_{2}^{P} = NP^{NP} \subseteq BQP^{BQP} = ...
- 51
4
votes
0
answers
129
views
Extending Fagin's Theorem to the Polynomial Hierarchy
Fagin's Theorem (see Wikipedia and these lecture notes) states that there is an equivalence between second-order logic (SOL) formulas with existential quantifiers, and problems in NP.
I was wondering ...
- 41
4
votes
0
answers
155
views
Maximum coloring of a graph with paths through uncolored vertices
Last night, I had a dream involving an intelligent spider which was only able to communicate by crawling around on a grid of words/phrases, like this one:
When I woke up, I wondered why some of the ...
- 281
4
votes
0
answers
69
views
Reachability games with banned vertex repetition
I have bumped into this problem while working on something model checking related and can't seem to find materials or efficient solutions for it. I couldn't even find a name for it.
We have a ...
- 41
4
votes
0
answers
2k
views
$NP = PSPACE$ and what that would mean about $PH$
So, a paper showed up on arXiv: https://arxiv.org/abs/1609.09562
The above states in the abstract that it contains a proof that $NP = PSPACE$
Since $NP \subseteq PH \subseteq PSPACE$, that would ...
- 3,810
3
votes
0
answers
67
views
NP-complete problem
Is the following line true?
Consider three problems A, B and C. If $A$ $<p$ $B$ and $B$ $<p$ $C$
and $B$ is NP-complete problem, then $C$ is also NP-complete.
If B is NP-complete, then C would ...
- 339
3
votes
0
answers
72
views
Karp hardness of a module in a graph
DEFINITION: A set of vertices $A\subseteq V$ in a graph $G(V,E)$ is called a module if it satisfies the following property:
For every $v\in V\setminus A$, either $A\subseteq N(v)$ or $A\cap N(v)=\...
- 2,313
3
votes
0
answers
236
views
Complete problems in NP∩coNP
I often read in Complexity literature that NP∩coNP is unlikely to have any complete problems. Is that unlikelihood "proved" ?
By proved, I mean that there would be a theorem that would relate the ...
- 362
2
votes
0
answers
91
views
Given a polynomial time approximation for expected chromatic number of random graph, can we show that P = NP?
Consider an Erdos-Renyi random graph $G(n, p)$. Suppose there exists a coloring algorithm $\mathcal{A}$ that, for any graph instance $g \sim G(n, p)$, generates a valid coloring $C^{\mathcal{A}}_g$ of ...
- 348
2
votes
0
answers
68
views
How can the approximation algorithm of one NP-complete problem be used to prove "the class P would be the same as the class NP"?
Recently, when I self-learnt Discrete Mathematics and Its Applications 8th by Kenneth Rosen, I had some questions about some statements in it.
Fur-
thermore, if a polynomial worst-case time ...
- 233
2
votes
0
answers
52
views
Reductions from 3-SAT that won't work directly from SAT
Our prof talked about why it's good to know that 3-SAT is NP-complete because it's easier to craft reductions from it than from plain SAT.
However, all the examples we've seen (reduction to ...
- 21
2
votes
0
answers
219
views
Exact Cover variant: partition a family of subsets into exact coverings
I have found that a problem that I'm analyzing is equivalent to the following variant of the Exact Cover problem:
Partition into $k$ Exact Covers
Input: A universe ...
- 111
2
votes
0
answers
127
views
Is it NP-hard to find different roots of different matrices simultaneously?
Consider the following problem:
input: pairwise distinct natural numbers $k_1,\dots,k_m$ that are all $\leq n$, and matrices $A_1,\dots,A_m \in \Bbb Q^{n \times n}$ where $m \leq n$.
output: a ...
- 21
2
votes
0
answers
73
views
How far would complexity hierarchies collapse if $L\in CoNP$ is $L\in NPH$?
Let $L\in CoNP$. Assuming that $L\in NPH$, what would we get?
So, as $L\in NPH$ then every language $A\in NP$ has a reduction $A \leq L$. This would mean that $\overline{L} \leq L$ as well. By ...
- 544