Questions tagged [np]
Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.
796 questions
0
votes
1
answer
45
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 ...
- 97
0
votes
0
answers
137
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
72
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
199
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
89
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
598
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
0
votes
0
answers
36
views
Communication complexity in Linear PCP
I wonder how should I state the communication complexity when having a linear PCP combined with another protocol?
May I ask that if I have a protocol that utilizes a linear PCP that has proof length n,...
- 101
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
191
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
124
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
172
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
119
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
81
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
1
vote
1
answer
80
views
What is the point of proof of correctness of NP-completeness?
In most the problems I am tasked to prove that a problem A is NP-complete. I show that B is in NP, then I reduce NP-hard problem A to B. Then I am required to prove that a yes instance in B is a yes ...
- 31
0
votes
2
answers
129
views
Graph contains two disjoint cliques
Is $$\text{2disjCLIQUEs} =
\left\{ \langle G, k_1, k_2 \rangle : \text{ the graph $G$ contains two disjoint cliques,one of size $k_1$, and the other of size $k_2$}\right\}$$ in $\texttt{P}$ or $\...
- 27