Questions tagged [np]

In computational complexity, NP is the complexity class consisting of problems whose yes instances can be verified in polynomial time. NP stands for 'nondeterministic polynomial time '.

Filter by
Sorted by
Tagged with
41 votes
4 answers
5k views

Why is "P vs. NP" necessarily relevant?

I want to start out by giving two examples: 1) Graham's problem is to decide whether a given edge-coloring (with two colors) of the complete graph on vertices $\lbrace-1,+1\rbrace^n$ contains a ...
Andreas Thom's user avatar
  • 25.3k
35 votes
1 answer
2k views

How hard is reconstructing a permutation from its differences sequence?

My interest in combinatorially motivated computational problems led me to search for simple problems that turn out to be computationally hard. In this pursuit, I came up with a problem which I hope is ...
Mohammad Al-Turkistany's user avatar
31 votes
3 answers
3k views

Given a polynomial-time algorithm, can we compute an explicit polynomial time bound just from the program?

Question. Given a Turing-machine program $e$, which is guaranteed to run in polynomial time, can we computably find such a polynomial? In other words, is there a computable function $e\mapsto p_e$, ...
Joel David Hamkins's user avatar
24 votes
4 answers
4k views

Super-linear time complexity lower bounds for any natural problem in NP?

Do we know any problem in NP which has a super-linear time complexity lower bound? Ideally, we would like to show that 3SAT has super-polynomial lower bounds, but I guess we're far away from that. I'd ...
Rune's user avatar
  • 2,386
22 votes
2 answers
6k views

$\mathbf{P} = \mathbf{NP}$, what's the problem?

Let's take the problem of the backpack: $A_1,\ldots ,A_n$ the weights that are integers, and we want to know if we can achieve a total weight of $V$. We take $$I=\dfrac{1}{2\pi}\int_0^{2\pi} \exp(-iVt)...
Dattier's user avatar
  • 3,737
21 votes
5 answers
5k views

Why relativization can't solve NP !=P?

If this problem is really stupid, please close it. But I really wanna get some answer for it. And I learnt computational complexity by reading books only. When I learnt to the topic of relativization ...
Ross Tang's user avatar
  • 571
21 votes
3 answers
6k views

Satisfiability of general Boolean formulas with at most two occurrences per variable

(If you know basics in theoretical computer science, you may skip immediately to the dark box below. I thought I would try to explain my question very carefully, to maximize the number of people that ...
Ryan Williams's user avatar
18 votes
7 answers
3k views

SAT and Arithmetic Geometry

This is an agglomeration of several questions, linked by a single observation: SAT is equivalent to determining the existence of roots for a system of polynomial equations over $\mathbb{F}_2$ (note ...
Vanessa's user avatar
  • 1,368
18 votes
5 answers
2k views

Equivalent forms of the P vs. NP problem

Many things in math can be formulated quite differently; see the list of statements equivalent to RH here, for example, with RH formulated as a bound on lcm of consecutive integers, as an integral ...
Michael's user avatar
  • 2,175
17 votes
5 answers
7k views

What techniques exist to show that a problem is not NP-complete?

The standard way to show that a problem is NP-complete is to show that another problem known to be NP-complete reduces to it. That much is clear. Given a problem in NP, what's known about how to ...
Qiaochu Yuan's user avatar
16 votes
4 answers
949 views

Representing mathematical statements as SAT instances

The following problem (call it THEOREMS) belongs to class NP. Input: Mathematical statement $S$ (written in some formal system such as ZFC) and positive integer $n$ written in unary. Output: "Yes" if ...
Bogdan's user avatar
  • 781
16 votes
2 answers
687 views

Is this kind of "Gerrymandering" NP-complete?

[I posted this on Math Stack Exchange about two weeks ago, but didn't get any reply, so I'm trying it here.] Consider the following simplified form of "Gerrymandering": You have $n^2$ ...
Frunobulax's user avatar
16 votes
2 answers
597 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
  • 163
14 votes
2 answers
3k views

Best-case Running-time to solve an NP-Complete problem

What is the fastest algorithm that exists to solve a particular NP-Complete problem? For example, a naive implementation of travelling salesman is $O(n!)$, but with dynamic programming it can be done ...
Claudiu's user avatar
  • 597
14 votes
2 answers
2k views

How did the Baker-Gill-Solovay paper come to be?

How did the Baker-Gill-Solovay paper come to be? Why were those three people talking together about "Relativizations of the $P=?NP$" question, and what was their collaboration like for the ...
user avatar
13 votes
3 answers
806 views

Undecidable infinite analogs of NP-complete problems?

In the paper Some undecidable problems involving edge-coloring of graphs, Burr proves that a certain k-coloring problems for certain infinite graphs (however, with finite descriptions - here "...
12 votes
2 answers
3k views

What impact would P!=NP have on the characterization of BQP?

Many complexity theorists assume that $P\ne NP.$ If this is proved, how would it impact quantum computing and quantum algorithms? Would the proof immediately disallow quantum algorithms from ever ...
user8347's user avatar
  • 267
12 votes
2 answers
420 views

Techniques for proving relaxed one-wayness of functions

Existence of one-way functions is a widely accepted conjecture in complexity theory. A function is one-way if it is computable in polynomial-time but not invertible in polynomial-time (this is ...
Mohammad Al-Turkistany's user avatar
11 votes
5 answers
4k views

Characterize P^NP (a.k.a. Delta_2^p)

What can you say about the complexity class $\text{P}^{\text{NP}}$, i.e. decision problems solvable by a polytime TM with an oracle for SAT? This class is also known as $\Delta_2^p$. Obviously $\text{...
Liron's user avatar
  • 203
11 votes
3 answers
1k views

Is there a polynomial-time algorithm for untangling the unknot?

I've found assertions that recognising the unknot is NP (but not explicitly NP hard or NP complete). I've found hints that people are looking for untangling algorithms that run in polynomial time (...
Peter Balch's user avatar
11 votes
3 answers
4k views

Is this a well known NP-complete problem?

I came across this problem recently and I wanted to know whether it was a well known NP-complete problem. I checked the library but could not find anything that matched exactly. Given a directed ...
Daniele's user avatar
  • 111
10 votes
0 answers
300 views

Testing contrasts in statistics: Is this provably a hard problem, or not?

Scheffé's method for identifying statistically significant contrasts is widely known. A contrast among the means $\mu_i$, $i=1,\ldots,r$ of $r$ populations is a linear combination $\sum_{i=1}^r c_i \...
Michael Hardy's user avatar
9 votes
3 answers
808 views

Conjecture on NP-completeness of tesselation of Wang Tile up to finite size

Motivated by these following questions on tessellation: coloring in lattice Reference for Wang Tile Computational approach deciding whether a set of Wang Tile could tile the space up to some size ...
user avatar
9 votes
3 answers
1k views

Is there a website or a survey collecting all NP-complete problems on graph theory?

I wonder whether there is a website or a survey collecting all known NP-complete or NP-hard problems on graph theory?
W. Paul Liu's user avatar
9 votes
3 answers
1k views

Non-existence of algorithm converting NP algorithm to P algorithm?

[Edit: in the light of Nate Eldredge's answer below I rephrase the question] P=NP is equivalent to the existence of a map of the following form: Input: a polynomial-time non-deterministic Turing ...
Tom Ellis's user avatar
  • 2,775
8 votes
4 answers
2k views

NP-hard problems in linear algebra and real analysis [closed]

I am curious about NP-hard problems in linear algebra and real analysis. An example in linear algebra would be the calculation of the permanent. I would thus like to collect in this thread a list of ...
8 votes
2 answers
3k views

How to find nearest lattice point to given point in R^n ? Is it NP ?

Consider some lattice in R^n. Take some point "P" in R^n (which does not belong to this lattice in general). What are the algorithms to find some nearest lattice point to "P" ? "Nearest" - means in ...
Alexander Chervov's user avatar
8 votes
2 answers
441 views

Is this problem on weighted bipartite graph solvable in polynomial time or it is NP-Complete

I encounter this problem recently and I want to know whether it is NP-Complete or solvable in polynomial time: Given a undirected weighted bipartite graph $G = (V, E)$ where $V$ can be partitioned ...
user9836's user avatar
  • 377
8 votes
1 answer
390 views

one-dimensional (sort of) tilings

Consider the following one-dimensional tiling problem. Each "tile" is a sequence of nonnegative integers. A "region" is also such a sequence. I can shift the "tiles", or reverse them. A tiling is ...
Cristopher Moore's user avatar
7 votes
3 answers
1k views

How slow are direct solutions of NP-complete problems on computers?

Sometimes I see that people call a problem NP-hard and because of that refuse to create computer algorithms that directly solve it. I think I've never read actual benchmark results for such problems. ...
CrabMan's user avatar
  • 171
7 votes
1 answer
2k views

Is pattern recognition NP-complete?

Hello, is the problem of pattern recognition (for a given sequence of n numbers, find the shortest Turing machine with an alphabet of 42 elements that will output these n numbers in, say, 5*n^3 time) ...
nibbles's user avatar
  • 233
7 votes
1 answer
743 views

$\mathit{NP}$-hard statements which are $\mathit{NP}$-complete under the Riemann Hypothesis

$\newcommand\NP{\mathit{NP}}\newcommand\SAT{\mathit{SAT}}\newcommand\CH{\mathit{CH}}\newcommand\PSPACE{\mathit{PSPACE}}$Are there $\NP$-hard problems which are $\NP$-complete under the Riemann ...
Turbo's user avatar
  • 13.7k
6 votes
1 answer
2k views

Closest vector problem (=nearest lattice point) is trivial for "reduced lattice" ?

Consider some lattice in R^n. Take some point "P" in R^n (which does not belong to this lattice in general). The problem is to find "nearest" lattice point. The problem is known NP-hard in general it ...
Alexander Chervov's user avatar
6 votes
1 answer
1k views

NP-hardness of a graph partition problem?

I'm interested in this problem: Given an undirected graph $G(E, V)$, Is there a partition of $G$ into graphs $G_1(E_1, V_1)$ and $G_2(E_2, V_2)$ such that $G_1$ and $G_2$ are isomorphic? Here $E$ is ...
Mohammad Al-Turkistany's user avatar
6 votes
0 answers
1k views

Is Logical Min-Cut Problem, NP-Complete? [closed]

Logical Min Cut (LMC) Problem: Suppose that G = (V, E) is an unweighted digraph, s,t are two vertices of V, and t is reachable from s. LMC Problem states that how we can make t unreachable from s by ...
valizadeh80's user avatar
6 votes
0 answers
460 views

Any approximation algorithms for self-avoiding walks?

I've a graph whose edges are weighted by probabilities, perhaps all equal. I would like to compute the overall probability of traveling between vertices x and y in the graph after I delete each edge ...
Jeff Burdges's user avatar
5 votes
2 answers
2k views

What impact would P=BQP have on NP?

Assuming P=BQP (ie we have polynomial time algorithms to solve all BQP problems) can we use it to prove that P=NP? The argument is that since we have the Grover's algorithm which can solve NP ...
rajeesh's user avatar
  • 61
5 votes
2 answers
243 views

Is it still not known whether the construction of shortest nonzero vector of a lattice w.r.t. $l^2$-norm is NP-hard?

It was shown in P. van Emde Boas, Another NP-complete partition problem and the complexity of computing short vectors in a lattice that the construction of a shortest nonzero vector of a Euclidean ...
taylor's user avatar
  • 425
5 votes
1 answer
538 views

Minimal Backtracking Proof Tree

When trying to prove that a particular instance of a problem like graph coloring or SAT is unsatisfiable, generally one explores the search tree using an algorithm like DPLL and the proof of ...
Opt's user avatar
  • 591
5 votes
0 answers
138 views

Are there sampNP-intermediate problems?

This questions is approximately cross-posted from theoretical computer science stackexchange Ladner's theorem establishes that if $\mathsf{P} \ne \mathsf{NP}$ then $\mathsf{NPI} := \mathsf{NP} \...
Vanessa's user avatar
  • 1,368
4 votes
1 answer
1k views

What arguments do exist against defining completeness in NP using injective Karp reductions?

It is crucial to use the right notion of reduction to define completeness inside NP. Different notions of completeness inside NP may have significant impact on the properties of complete languages. ...
Mohammad Al-Turkistany's user avatar
4 votes
1 answer
1k views

BPP being equal to #P under Oracle

Luca Trevisan here gives a randomized polynomial-time approximation algorithm for #3-coloring given an NP oracle. In a similar vein, I was wondering if there were any results on $BPP^{NP}\stackrel{?}{...
Opt's user avatar
  • 591
4 votes
4 answers
739 views

How to find the $\pm 1$ vector that is closest to a given vector $(r_1, \dots, r_l)$? Is it in NP? What algorithms are available?

Given a real vector $R = (r_1, \dots, r_l)$ and a set of $n$ distinct vectors $$\begin{array}{c} V_1 = (c_{1,1}, \dots, c_{1,l})\\ V_2 = (c_{2,1}, \dots, c_{2,l})\\ \vdots\\\ V_n=(c_{n,1}, \dots, c_{...
Alexander Chervov's user avatar
4 votes
1 answer
341 views

Lower bound on the number of solutions of 2SAT

To compute the number of solutions of a 2SAT is a hard problem. Is there some nontrivial lower or upper bound on this number in terms of a “coarse-grained” description of the Boolean formula, for ...
Alm's user avatar
  • 1,159
4 votes
1 answer
1k views

Simple example of why Differential Equations can be NP Hard [closed]

Just looking for a simple example of why Differential Equations can be NP hard Edit: It appears that the answer below may be what I was looking for, but I am clarifying just in case: Slides 58--...
user2908444's user avatar
4 votes
1 answer
244 views

Constructing hard inputs for the complement of bounded halting

If there is always a hard input for the complement of bounded halting, can that input be constructed? More precisely, suppose that for any deterministic TM $M$ accepting $$ \text{coBHP}=\{\...
Hunter Monroe's user avatar
4 votes
0 answers
175 views

Is the Weber problem a NP-hard problem?

The Weber problem is a special case of a facilities location problem : In a basic formulation, the facility location problem consists of a set of potential facility sites L where a facility can be ...
Julien's user avatar
  • 141
3 votes
1 answer
886 views

Root of polynomials in a finite field

I am looking for a way to find out if a polynomial $P\in \mathbb Z/p\mathbb Z=\mathbb F_p$, of great degree, has roots in $\mathbb F_p$, with $p$ a big prime number. For example : $p=2^{2020}-69$ ...
Dattier's user avatar
  • 3,737
3 votes
2 answers
206 views

(How) do Better TSP Heuristics help in Answering the $NP=P$ Question?

This question is motivated by my impression, that finding better heuristics for the TSP problem (or any other $NP$-complete problem) is "only" of practical interest, but doesn't provide any progress ...
Manfred Weis's user avatar
  • 12.6k
3 votes
1 answer
214 views

NP-hardness of finding maximum of minimum element in diagonal of a matrix

For $A = \{a_{ij}\} \in R^{n\times n}$, is finding $$ \max_{\sigma \in S_n}\min_{1 \le i \le n} a_{i,\ \sigma_i} $$ NP-hard?
Yuan Gao's user avatar
  • 163