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
457
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 ...
- 18.6k
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
1
vote
1
answer
169
views
Why is infeasibility of linear programming considered to be an NP problem?
I recently came across this question, and the way I think people usually go about this is to find a certificate that answers 'yes' to the decision problem 'Is this LP infeasible?' Or, given a ...
CommunityBot
- 1
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.
...
1
vote
2
answers
150
views
What are the necessary requirements for proving NP is closed under complement?
I've had the following question on a test and I answered: 'False', my answer was incorrect and I'm trying to understand why.
$VC = \{<G,k> |\ G =$ undirected graph with a vertex cover of size $k\...
CommunityBot
- 1
2
votes
1
answer
146
views
How to prove $\textbf{NP}\neq \textbf{DTIME}(2^{\sqrt{n}})$?
I want to prove that $\textbf{NP}\neq \textbf{DTIME}(2^{\sqrt{n}}).$
My thoughts is: it seems easy since $$NP=\cup_{c\in\mathbb{N}}\text{NTIME}(n^c)$$
and we can say they aren't equal.
is there any ...
- 37
3
votes
1
answer
882
views
Is quadratic nonresiduosity in $\textbf{NP}$?
The paper "The Knowledge Complexity of Interactive Proof Systems" uses the language of quadratic nonresidues defined via the following excerpt from page 293 as an example of constructing an ...
D.W.♦
- 169k
1
vote
1
answer
334
views
Show problem is NP-hard
I'm preparing for my exam and I got stuck on the following problem:
The gardening problem:
We have access to a set of different types of seeds and a number of plant pots.For each plant pot, there is ...
CommunityBot
- 1
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 ...
- 18.6k
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,661
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)$ ...
- 3,669
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
5
votes
1
answer
1k
views
Is 3-UNSAT problem coNP-complete?
The 3-SAT problem, i.e. the problem whether a given Boolean formula consisting of clauses of at most 3 literals is known to be NP-complete. Then it’s complement, i.e. whether such a formula is ...
CommunityBot
- 1
0
votes
1
answer
128
views
How to show $\mathsf{NP^{BQP} = QMA}$?
I was reading the document below, authored by @Lieuwe Vinkhuijzen.
In equation 2.1 (page 14 of this), the following equation is mentioned.
$$\mathsf{\Sigma_1^{BQP} =NP^{BQP}= QMA}$$
$\mathsf{NP}$, $\...
- 229