# Questions tagged [np]

NP stands for Nondeterministic Polynomial time.

104 questions
Filter by
Sorted by
Tagged with
122 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 ...
90 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-...
139 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 ...
88 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 ...
245 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: ...
334 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 ...
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?
240 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 ...
443 views

113 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 ...
131 views

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 $\... 0answers 189 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 ... 2answers 307 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 ... 2answers 172 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 ... 2answers 163 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 ... 0answers 120 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 ... 0answers 140 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, ... 1answer 83 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 ... 1answer 390 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? 2answers 688 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 ... 2answers 537 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 ... 2answers 395 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 ... 2answers 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$-... 1answer 190 views ### Is there any relationship of hardness between the two problems? Assuming F(x,y,D) is a function, and we can evaluate it in polynomial time with input x, y and D. Consider the problem P1: With D as input, computes$(x^*,y^*)=argmax_{(x,y)}F(x,y|D)$where x and y ... 2answers 298 views ### Questions regarding SETH I read about the strong exponential time hypothesis, which states (as far as I understand) that SAT problem cannot be solved in running time$O(2^{\epsilon n})$for any$\epsilon < 1$, where$n$is ... 1answer 167 views ### Is sparse embedding of a NP-complete problem in a polynomial problem NP-complete? Consider the following problem P: Input is a finite graph G. If the number of vertices in G is 2^2^i for some integer i, then output a minimum vertex cover of G; otherwise output empty set. Can I say ... 0answers 93 views ### About representability of optimization versions of NP-complete questions as polynomial optimization over the hypercube Naively, in my very limited awareness, it feels that the Max-CUT is a very "special" NP-Hard problem because for a graph with edge-set$E$, it can be written as the question of trying to maximize a$n$... 1answer 167 views ### Analogues of the Berman Hartmanis conjecture and the Creativity Hypothesis The Berman Hartmanis conjecture which formally states that there is an isomorphism for two$NP$complete languages$L_{1}$, and$L_{2}$, the isomorphism is a bijective function$f()$such that$f()$... 1answer 164 views ### Does p-isomorphism preserve phase transition? Consider two NP-complete languages that are polynomial-time isomorphic. If we know that one of them exhibits phase transition (with respect to some order parameter), does this imply that the other ... 0answers 111 views ### An NP-complete variant of factoring and relation to factoring [closed] After reading this post An NP-complete variant of factoring. I come up with a question. To summerize the post, we have the factoring problem (F) which ask for a number$p$that is prime and divides ... 1answer 104 views ### non deterministic algorithm always find the right solution? [closed] i'm confused since i see some books mention the NP time algorithms as "very lucky" that means it always finds the right path? also can someone explain the coming points to me please... A ... 1answer 735 views ### Intersection of languages in NP Can intersection of two languages in NP which are not NP complete be NP complete? Can intersection of two languages in coNP which are not coNP complete be coNP complete? Can intersection of two ... 0answers 177 views ### Are ill-posed inverse problems in NP? I'm a physicist who works on inverse problems; I'll explain what these are by means of an example. Consider an object whose refractive index is known; then, the problem of computing scattered ... 3answers 428 views ### Natural NP-complete problems with high density? (This question is related to a previous one, see the discussion in "Almost easy" NP-complete problems, but it may also be of independent interest, so I post it as a separate question.) Let ... 0answers 227 views ### Complexity of a problem over acyclic context-free grammars Let$G$be an acyclic, context-free grammar over a fixed alphabet$\Sigma=\{a_1,\dots,a_k\}$with the restriction (without loss of generality) that$|w|=2$for each rule$A\to w$in the grammar. ... 2answers 1k views ### Is there a non-deterministic linear time algorithm for CNF-SAT? The decision problem CNF-SAT can be described as follows: Input: A boolean formula$\phi$in conjunctive normal form. Question: Does there exist a variable assignment that satisfies$\phi$? I'm ... 1answer 209 views ### What do dichotomy theorems feed on? It is well known that certain classes of NP-problems have dichotomy theorems, which guarantee that every task in the class is either NP-complete or is in P. The best known such result is Schaefer's ... 0answers 103 views ### Functional oracles In the traditional oracle Turing machine, the oracle is specified as a decision problem. Roughly speaking, one puts a string in the oracle tape, and asks whether it is true or false. I am wondering ... 3answers 961 views ### How much would a SAT oracle help speeding up polynomial time algorithms? Access to a$SAT$oracle would provide a major, super-polynomial speed-up for everything in${\bf NP}-{\bf P}$(assuming the set is not empty). It is less clear, however, how much would$\bf P$... 0answers 174 views ### Question about a unary language construction For any language$L$, let us define another language$Tally(L)$, as follows: $$Tally(L)=\{1^n\;|\;\exists x \;\mbox{with}\; x\in L \;\mbox{and}\; |x|=n\}$$ That is,$Tally(L)$encodes whether there is ... 1answer 650 views ### If BQP contains NP, does this mean that P=NP? There is a question raised by Scott Aaronson in one of his papers [1]: "Could we show that if NP ⊆ BQP, then the polynomial hierarchy collapses?". Assuming the answer is yes, and it is also know that ... 1answer 256 views ### Is finding whether k different perfect matchings exist in a bipartite graph co-NP? Few definitions first. The co-NP problem is a decision problem where the answer "NO" can be verified in polynomial time. The perfect matching in a bipartite graph is a set of pairs of nodes (a pair is ... 0answers 272 views ### Finding an equivalent NP-complete instance for this game-theory problem I apologize if this question is not a good fit for CSTheory. I'm a PhD student who has just started out and I'm working on a game-theory problem in one of my classes. Although my professor hasn't ... 0answers 920 views ### Is there a reduction from a 0-1 knapsack problem to the unbounded problem? As we know, an unbounded knapsack problem could be described as:$\max \sum_{i=1}^nc_1x_i$s.t.$\sum_{i=1}^na_ix_i\le bx_i\ge0,x_i\in\mathbb Z,i=1,\cdots,n$And for an 0-1 knapsack problem, we ... 1answer 521 views ### Integer linear programming in logarithmic number of variables I read that integer linear programming is solvable in polynominal time if the number$n$of variables is fixed, i.e.$n \in O(1)$. If the number of variables grows logarithmically, i.e.$n \in O(\...
Proof complexity is a most basic area of computational complexity theory. An ultimate purpose of this area is to prove $NP\neq coNP$, that is, any prover cannot give a proof of unsatisfiability of ...