Questions tagged [np]

NP stands for Nondeterministic Polynomial time.

Filter by
Sorted by
Tagged with
1 vote
0 answers
71 views

Separating disjoint PSPACE-hard sets by NP-separators (and some variants)

I am trying to find some references or arguments for results of the form, where $X,Y$ vary over complexity classes, typically with $X\subseteq Y$, and $A,B$ are disjoint languages that are $Y$-hard: ...
Anupam Das's user avatar
0 votes
0 answers
65 views

Reductions That Acts on Witnesses

We say that a language $X$ is polynomial time reducible to $Y$, intuitively, if given an algorithm for solving $Y$, there's an algorithm for solving $X$. I know this can be formalized using Karp ...
Boran Erol's user avatar
0 votes
0 answers
44 views

Unbounded Knapsack: Does Increasing capacity increase optimal value?

Our decision problem is as follows: given weights $\mathbf{w}$, values $\mathbf{v}$, and capacities $C_1$ and $C_2$, where $C_1 < C_2$, does the optimal value of unbounded knapsack with the above ...
happyfeet's user avatar
0 votes
0 answers
83 views

Is there a Hidden subgroup problem in BQP but suspected not to be in NP?

Wikipedia lists HSP problems in abelian and non-abelian groups. So does the following (extensive) compedium. I searched and found none is a BQP-complete (or even BQP-hard) problem. There has been a ...
108_mk's user avatar
  • 225
-1 votes
1 answer
134 views

Solve 3CNF in Poly-Time with Satisfiability Oracle

The problem: Given an algorithm A which can tell whether any 3CNF formula is satisfiable in poly-time, develop an algorithm B that calculates a solution for the formula, also in poly-time, using A as ...
Dilara's user avatar
  • 1
11 votes
1 answer
905 views

Status of András Faragó’s (second) claimed proof that NP=RP

In 2020, András Faragó claimed to have proved that NP = RP (discussion; v1 of the paper); the paper was later retracted due to a counterexample to theorem 1. A few days ago, Faragó posted another ...
Jiak Kantang's user avatar
1 vote
0 answers
70 views

Hardness for find the clause for statisfiable 3-SAT problems

The 3-SAT problems are known to be NP-complete so the decision problems are believed to be non efficiently solvable unless P=NP. Yet, there are cases where the satisfiability can be answered such as ...
ironmanaudi's user avatar
4 votes
1 answer
281 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 ...
Colonizor48's user avatar
5 votes
1 answer
156 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, ...
user3508551's user avatar
  • 1,153
2 votes
1 answer
158 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?
Turbo's user avatar
  • 12.9k
7 votes
1 answer
158 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 ...
Noel Arteche's user avatar
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 ...
Command Master's user avatar
1 vote
0 answers
85 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)},\ \...
Soham Chatterjee's user avatar
3 votes
1 answer
93 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 ...
wavosa's user avatar
  • 133
-3 votes
1 answer
98 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 ...
user68029's user avatar
-1 votes
1 answer
121 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 ...
ryu576's user avatar
  • 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$ ...
Mark S's user avatar
  • 1,083
-1 votes
1 answer
163 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 ...
user1868607's user avatar
  • 1,017
0 votes
1 answer
114 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 ...
Hang Chen's user avatar
  • 111
1 vote
1 answer
259 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 ...
Würthi's user avatar
  • 33
9 votes
1 answer
213 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 ...
M.Monet's user avatar
  • 1,429
1 vote
0 answers
153 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=\{...
Turbo's user avatar
  • 12.9k
2 votes
1 answer
159 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 ...
Russell Easterly's user avatar
6 votes
1 answer
895 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?
Botanicus's user avatar
1 vote
1 answer
148 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$ ...
borroot's user avatar
  • 13
1 vote
0 answers
110 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 ...
Turbo's user avatar
  • 12.9k
1 vote
1 answer
464 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$ ...
Ivy's user avatar
  • 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, ...
kodlu's user avatar
  • 2,070
11 votes
1 answer
297 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?
Jérôme Verstrynge's user avatar
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 ...
Jérôme Verstrynge's user avatar
-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.
oompa's user avatar
  • 101
-3 votes
1 answer
249 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,...
Refrain's user avatar
  • 67
0 votes
2 answers
504 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 ...
Samuel Barr's user avatar
3 votes
2 answers
134 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 ...
Jérôme Verstrynge's user avatar
0 votes
0 answers
148 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-...
gifa's user avatar
  • 21
2 votes
0 answers
150 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 ...
Turbo's user avatar
  • 12.9k
-3 votes
1 answer
290 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 ...
Bert Langton's user avatar
0 votes
3 answers
868 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: <...
Jérôme Verstrynge's user avatar
7 votes
1 answer
365 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 ...
Jake Thomas's user avatar
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?
user2925716's user avatar
10 votes
0 answers
275 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 ...
PHD candidate's user avatar
12 votes
0 answers
505 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 $\...
Mason's user avatar
  • 229
-1 votes
2 answers
2k 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}) \...
TDThu's user avatar
  • 7
6 votes
1 answer
125 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 ...
Zur Luria's user avatar
  • 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 $\...
Alberto M.'s user avatar
4 votes
0 answers
231 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 ...
Michael Wehar's user avatar
4 votes
2 answers
353 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 ...
Jasper Lu's user avatar
3 votes
2 answers
195 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 ...
Myath's user avatar
  • 141
1 vote
2 answers
258 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 ...
Mohammad Al-Turkistany's user avatar
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 ...
Samuel Schlesinger's user avatar