Questions tagged [np]
Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.
797 questions
3
votes
1
answer
456
views
Has any problem been non-constructively proven to be in NP?
I believe that a standard way to prove that a language $L$ is in NP is to explicitly construct a witness $y$ for any instance $x$ in $L$ and an efficient algorithm that uses the witness to show that ...
- 1,216
0
votes
0
answers
21
views
Is Nondeterministic Quasi-polynomial($\mathsf{NqP}$) in Polynomial Hierarchy ($\mathsf{PH}$)?
Nondeterministic quasi-polynomial time ($\mathsf{NqP}$) is defined as a set of decision problems that can be decided by a nondeterministic Turing machine making a number of steps bounded above by $T(n)...
- 229
0
votes
0
answers
25
views
Does a pseudopolynomial reduction imply weak NP-hardness?
I am trying to reason about weak NP-hardness using pseudopolynomial reductions.
Suppose:
Problem A is weakly NP-hard.
There exists a pseudopolynomial-time reduction from A to another
problem B.
...
0
votes
1
answer
94
views
Definition of search-NP and search-P
Recall that a language $A$ is in NP iff it is of the form $$A = \{x \in \Sigma^* : (\exists w\in\Sigma^*)\ (x, w) \in R_A\},$$ for some relation $R_A$ such that membership of $(x, w)\in R_A$ can be ...
- 109
0
votes
0
answers
141
views
Complexity class of $\#\mathrm{P}$-hard counting problem can be reduced to $\#\mathrm{P}$ given its own output for different values
I have a counting problem that famously has evaded being solved by simply counting the elements of a set and somehow seemed to have involved subtraction in an essential way (it is in $\mathrm{GapP}^+$,...
- 133
0
votes
1
answer
87
views
Why formulate P vs NP in terms of binary strings?
Let $L \subset \sigma^*$ be a decision problem. An Algorithim M is a polynomial bounded verifier for $L$, when:
M has a polynomial bounded run time
$M(x,z)$ the output on the the input $x \text{#} z$....
1
vote
1
answer
222
views
Can we solve Parity Games in polynomial time given this subroutine?
Parity games are simple games played on a graph: https://en.m.wikipedia.org/wiki/Parity_game
Let $A$ be an algorithm that solves the following problem in polynomial time.
Given: A graph $G=(V,E)$ ...
- 55
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
3
votes
1
answer
608
views
What is the class of problems that can be efficiently approximated?
Consider the class NP of problems whose solutions can be verified in polynomial time. For some problems in NP, there may not be polynomial algorithms that solve them.
However, in practice, it is ...
- 165
4
votes
2
answers
2k
views
Are all problems in P reducible to each other and equally difficult?
Can every problem $ A \in P $ be reduced to any other problem $ B \in P $? If so, does that mean all problems in $ P $ have the same level of difficulty? Does this also hold for other complexity ...
- 55
1
vote
1
answer
229
views
Why is P = PSPACE, if P = NP?
I understand that we have the inclusions $P \subseteq NP \subseteq PSPACE$ . If we assume $ P = NP$ , this means that every problem in NP can be solved in polynomial time by a deterministic Turing ...
- 55
2
votes
1
answer
145
views
Show that rectangle packing is NP-complete
I have this problem:
Given a finite set of rectangles R, and a rectangle P, show that the problem of fitting R's rectangles inside P so that no two rectangles of R overlap and all their sides are ...
0
votes
2
answers
201
views
Cook Levin theorem proof - question regarding the polynimal time analysis
Recently I've learned the proof of the theorem that use verifiers and construct the boolean expression depand on the machine that decide the verifier in polynomial time.
The question is probably ...
0
votes
1
answer
125
views
Why we need the assumption P=NP for this problem?
There is a famous problem that we can prove that if $P=NP$, then any non-trivial language $A \in P$ is NP- complete.
The proof idea was to use non- triviality of $A$. So we say that as $A$ is non-...
- 39
0
votes
1
answer
94
views
Clarifying an interpretation of the definition of the subset-sum problem
I recently heard about the subset-sum problem, and its definition got me thinking.
Is it true that, to answer "yes" to a specific instance of the subset-sum problem, an explicit subset also ...
- 103