Questions tagged [np]
NP stands for Nondeterministic Polynomial time.
131
questions
3
votes
1
answer
146
views
is SUBEXP contained within PSPACE?, NP?
Let SUBEXP is the complexity class of all problems solvable in sub-exponential time in the length of the input. What are the known properties of this class? Is it known to be contained in PSPACE, if ...
- 321
5
votes
1
answer
153
views
Are there complexity teaching resources that do not treat NP-hardness gadgets as Voodoo magic?
I am teaching a mini-complexity course to high achieving high-school students from my country this fall, and they have all expressed strong interest in learning more about what $P, NP$, reductions, ...
- 1,078
2
votes
1
answer
98
views
CVP to SVP reduction?
The notes here provide a reduction from $SVP$ to $CVP$ https://people.csail.mit.edu/vinodv/COURSES/CSC2414-F11/L4.pdf.
Is there a reduction in the reverse direction?
- 12.8k
7
votes
1
answer
152
views
Conversion between NP certificates
This might be a well-known fact, but I can't convince myself of whether this is true.
Suppose I have some NP language and two different verifying procedures V and V' for L. For any x in L, is it the ...
- 801
7
votes
2
answers
1k
views
Problems in NP with non-trivial certificate
For all NP-complete problems I can think about, the problem statement says very clearly how to test a certificate. I'm looking for interesting problems with NP which have non-trivial certificates. I ...
- 464
1
vote
0
answers
82
views
$NP\subseteq P/poly\implies PH\subseteq P/poly$ [closed]
We know if $NP\subseteq P/poly$ then $PH=\Sigma_2$ Then We want to show that $\Sigma_2-SAT\in P/poly$. Now $$\phi\in \Sigma_2-SAT\iff \exists\ x\in\{0,1\}^{p_1(n)}\ \forall\ y\in \{0,1\}^{p_2(n)},\ \...
- 288
3
votes
1
answer
89
views
END OF THE LINE problem finding a node with in-degree $0$ or out-degree $0$ depending on the initial node
The END OF THE LINE problem is stated as
Given two circuits, P and N, a node, v, is balanced if $P(N(v)) = N(P(v)) = v$ or $P(N(v)) \neq N(P(v)) \neq v$. Given that $0^n$ is not balanced, find ...
- 135
-3
votes
1
answer
96
views
Why if non determinism adds no power at all to DFAs or to Turing machines, why is it that most people beleieve P != NP [closed]
During Theory of Computation or Automata Theory or the equivalent class at my University, I was shown that non deterministic and deterministic automata can solve the exact same set of problems, then ...
-1
votes
1
answer
112
views
Does the set $P$ contain only decision problems or also optimization problems? [closed]
Looking at many posts on Stack Overflow, it seems the set $P$ has only decision problems. See for instance the accepted answer here.
But, this seems to be in contradiction to the book Introduction to ...
- 109
0
votes
0
answers
122
views
Can an NP-search problem be defined non-constructively?
Given a random two-to-one function $f(x)$ from $n$ bits to $n$ bits, consider the following search problem:
Find a polynomial number of pairs $(d,y)\in \{0,1\}^n\times\{0,1\}^n$ with $d\ne \bf 0$ ...
- 1,063
-1
votes
1
answer
150
views
Cook's theorem and universal machine
From Papadimitriou and Yannakakis, "A Note on Succinct Representations of Graphs" second parragraph of the proof of the main result.
Cook (1971) presented in his classical paper a ...
- 921
0
votes
1
answer
113
views
Can one find any solution to this matrix problem in polynomial time?
I am given an M * N (M > 1, N > 1) matrix with all the numbers blackened but their row and column sums are visible.
For example, I am given this 3 * 3 matrix.
And one of the possible matrix ...
- 111
1
vote
1
answer
243
views
What if NP = coNP?
Are there any major implications of NP = coNP (if true) the way there would be if P=NP? I'm thinking of real-world implications analogous to the encryption-pocalypse (excuse the drama) that would ...
- 33
9
votes
1
answer
197
views
Enumerating finite set of words with Hamming distance $1$
Consider the following problem:
INPUT: a finite set $W$ of words over binary alphabet, all words have the same length.
OUTPUT: yes if there exists a permutation of $W$ such that any two consecutive ...
- 1,227
1
vote
0
answers
147
views
Relation between BSS and Turing models
$P_\mathbb R$ is the set of languages decidable in polynomial time over the real $BSS$ machine defined in https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine.
Let $0-1-P_\mathbb R=\{...
- 12.8k
2
votes
1
answer
152
views
Short UNSAT Certificates for X3SAT
Exactly 1 in 3 SAT ($X3SAT$) is a variation of the Boolean Satisfiability problem. Given an instance of clauses where each clause has three literals, is there a set of literals such that each clause ...
- 549
6
votes
1
answer
766
views
Reducing #SAT to MAJ-SAT
In this post (Lower bounds on #SAT?) it says: "given an algorithm for Majority-SAT, one can solve #SAT with $O(n)$ calls to the algorithm."
What is the approach to this?
- 87
1
vote
1
answer
142
views
Complexity of a satisfiability problem
I would like the know the complexity of a specific satisfiability problem. I have a feeling it could be solved in polynomial time, but I am not sure about it. The problem is described below.
Given $n$ ...
- 13
1
vote
0
answers
109
views
On proving the standard $p$-measure on $NP$ assumption?
In the answer here An Anthology of Complexity Assumptions an interesting assumption is made. The assumption is $p$-measure of $NP$ is not $0$. There are many non-trivial consequences that follow from ...
- 12.8k
1
vote
1
answer
447
views
Is the knapsack variant with small profit and unlimited repetition of items NP-hard?
Consider the unbounded Knapsack problem where we are given $n$ items of integral weights $w_i$, integral profits $p_i$, and a max weight $W$. The goal is to maximize the total profit $\sum_i x_ip_i$ ...
- 29
22
votes
3
answers
7k
views
Implications of proving NP=RP on complexity theory
Edit: As indicated below by Mahdi Cheraghchi and in the comments, the paper has been withdrawn. Thanks for the multiple excellent answers on the implications of this claim. I, and hopefully others, ...
- 2,070
11
votes
1
answer
295
views
When was co-NP introduced for the first time?
My best finding is Pratt's 1975 article. Is there any earlier mention of co-NP?
2
votes
0
answers
198
views
Who introduced the notion of Non-Deterministic Polynomial time?
In his 1972 paper, Richard Karp provides a definition of NP (section 3, definition 4, p.91). It this the original definition of the class NP or is there a previous one?
Edit
Edmonds mentions the idea ...
-4
votes
1
answer
32
views
Polynomial-time reducibility of Primality and 3-SAT
Is 3-SAT $\leq_{p}$ Primality? And/or is Primality $\leq_{p}$ 3-SAT? I think the answer is no and yes, respectively, but I'm not sure. Any help would be appreciated.
Thank you.
- 101
-3
votes
1
answer
242
views
is this selection problem np-hard? [closed]
Give $n$ clusters $C=\{C_i\}_{i=1}^n$ where each cluster consists of a set of similar points, i.e., $C_i=\{c_j\}_{j=1}^{|C_i|}$. The similarty between two points $c_i$ and $c_j$ is denoted as $w(c_i,...
- 67
0
votes
2
answers
494
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 ...
- 129
3
votes
2
answers
129
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 ...
0
votes
0
answers
146
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-...
- 21
2
votes
0
answers
149
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 ...
- 12.8k
-3
votes
1
answer
267
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 ...
0
votes
3
answers
779
views
Hamiltonian cycle vs co-NP [closed]
I am trying to understand co-NP and its implications properly.
The French Wikipedia page describing co-NP provides the "complementary" version of the Hamiltonian cycle in co-NP as follows:
<...
7
votes
1
answer
364
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 ...
- 71
18
votes
1
answer
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?
- 317
10
votes
0
answers
274
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 ...
- 101
12
votes
0
answers
503
views
Is satisfying $\sum_{i=1}^{n}{x_i^{y_i}}=r$ NP Complete?
Question
I would like to show that satisfying $\sum_{i=1}^{n}{x_i^{y_i}}=r$ is NP-Complete.
Consider $L= \{(\bar{y},r):\exists \bar{x} \text{ such that } \sum_{i=1}^{n}{x_i^{y_i}}=r\}$.
Where $\...
- 229
-1
votes
2
answers
1k
views
Are these problems in NP class?
${\bf New\ version}$ [Version 1.2]
Let $f: \mathbb{N} \to \{0,1\}$ be a computable function, ${\bf Fin}(\mathbb{Z})$ be the set of all finite subsets of $\mathbb{Z}$, and $W: {\bf Fin}(\mathbb{Z}) \...
- 7
6
votes
1
answer
121
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 ...
- 359
5
votes
1
answer
140
views
Path in a graph with durations [closed]
I have the following problem:
given
a directed graph $G=(V,E,d)$, where $d:V\to\mathcal{I}(\mathbb{Q}_0^+\cup\{+\infty\})$ (here $\mathbb{Q}_0^+$ denotes the set of non-negative rationals and $\...
- 151
4
votes
0
answers
229
views
Is $NEXP^{NP}$ known to not be contained in $NP/poly$?
To the best of my knowledge, it is known that $NEXP^{NP} \nsubseteq P/poly$, but it's still not known if $NEXP \nsubseteq P/poly$.
For more info, see "Superpolynomial circuits, almost sparse oracles ...
- 5,127
4
votes
2
answers
349
views
NP-hardness of finding 0-1 vector to maximize rows of {-1, +1} matrix
Consider the following discrete optimization problem: given a collection of $m$-dimensional vectors $\{ v_1, \dots, v_n \}$ with entries in $\{-1, +1\}$, find an $m$-dimensional vector $x$ with ...
- 41
3
votes
2
answers
193
views
Reduction of graph chromatic number to hypergraph 2-colorability
I'm following this paper titled "Coverings and colorings of hypergraphs" by Lovasz 1973, which is referenced in Garey and Johnson's Computers and Intractability, for the Set Splitting Problem. In this ...
- 141
1
vote
2
answers
254
views
Complexity of a variant of partition problem
Motivated by this post, Strongly NP-complete variants of subset sum or partition problem, I am interested in this variant of partition:
Given a solution to balanced partition problem (both parts have ...
- 20.8k
2
votes
0
answers
125
views
What are some known methods for showing that a class has no complete problems?
The only way that I know of is the way that you can show that $RE \cap coRE$ does not via diagonalization. Mostly curious because if $NP \cap coNP$ has no complete problems then $P \neq NP$. I tried ...
- 1,572
1
vote
0
answers
147
views
Co-Partition Problem: Why is this proof for it being in NP wrong? [closed]
So I have this wrong proof that the problem "Co-Partition" is in NP. I know the proof is wrong because I've encountered it in an educational environment and was told that it's not working. I don't, ...
- 11
1
vote
1
answer
154
views
Why does not the definition of NP problems care about the complexity of guessing? [closed]
I have a question regarding the definition of NP problems. According to that, a problem is in NP if one can guess a certificate of polynomial size in polynomial time. However, this definition does not ...
- 27
8
votes
1
answer
892
views
Is $\sf{P^{NP \cap coNP}} = \sf{NP \cap coNP}$?
If it is unknown, are there reasons to believe that they might not be equal?
- 137
14
votes
2
answers
746
views
Are There Highly Symmetric NP- or P-complete Languages?
Does there exist $L$, an NP- or P-complete language which has some family of symmetry groups $G_n$ (or groupoid, but then the algorithmic questions become more open) acting (in polynomial time) on ...
- 1,572
12
votes
2
answers
825
views
Euclidean TSP in NP and square root complexity
In this lecture notes by Ola Svensson: http://theory.epfl.ch/osven/courses/Approx13/Notes/lecture4-5.pdf, it is said that we don't know if Euclidean TSP is in NP:
The reason being that we do not ...
- 363
15
votes
2
answers
483
views
(How) Could we discover/analyze NP problems in the absence of the Turing model of computation?
From a purely abstract math/computational reasoning point of view, (how) could one even discover or reason about problems like 3-SAT, Subset Sum, Traveling Salesman etc.,? Would we be even able to ...
- 5,255
25
votes
2
answers
1k
views
Is there an NP-complete language that contains precisely half of the n-bit instances?
Is there a (preferably natural) NP-complete language $L\subseteq \{0,1\}^*$, such that for every $n\geq 1$
$$|L\cap \{0,1\}^n|=2^{n-1}$$
holds? In other words, $L$ contains precisely half of all $n$-...
- 11.3k