# Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

129 questions
Filter by
Sorted by
Tagged with
25k views

### Problems Between P and NPC

Factoring and graph isomorphism are problems in NP that are not known to be in P nor to be NP-Complete. What are some other (sufficiently different) natural problems that share this property? ...
5k views

### An NP-complete variant of factoring.

Arora and Barak's book presents factoring as the following problem: $\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\}$ They add, further ...
• 3,946
9k views

### NP-hard problems on trees

Several optimization problems that are known to be NP-hard on general graphs are trivially solvable in polynomial time (some even in linear time) when the input graph is a tree. Examples include ...
• 10.6k
14k views

### Is finding the minimum regular expression an NP-complete problem?

I am thinking of the following problem: I want to find a regular expression that matches a particular set of strings (for ex. valid email addresses) and doesn't match others (invalid email addresses). ...
• 1,336
7k views

### Many-one reductions vs. Turing reductions to define NPC

Why do most people prefer to use many-one reductions to define NP-completeness instead of, for instance, Turing reductions?
• 1,668
7k views

### What would be the consequences of factoring being NP-complete?

Are there any references covering this?
• 803
2k views

### When does "X is NP-complete" imply "#X is #P-complete"?

Let $X$ denote a (decision) problem in NP and let #$X$ denote its counting version. Under what conditions is it known that "X is NP-complete" $\implies$ "#X is #P-complete"? Of course the existence ...
• 4,258
1k views

### How does the Mulmuley-Sohoni geometric approach to producing lower bounds avoid producing natural proofs (in the Razborov-Rudich sense)?

The exact phrasing of the title is due to Anand Kulkarni (who proposed this site be created). This question was asked as an example question, but I’m insanely curious. I know very little about ...
• 2,035
2k views

### DNA-algorithms and NP-completeness

What is the relationship between DNA-algorithms and the complexity classes defined using Turing machines? What do the complexity measures like time and space correspond to in DNA-algorithms? Can they ...
• 283
4k views

10k views

### Is optimally solving the n×n×n Rubik's Cube NP-hard?

Consider the obvious $n\times n\times n$ generalization of the Rubik's Cube. Is it NP-hard to compute the shortest sequence of moves that solves a given scrambled cube, or is there a polynomial-time ...
• 23.1k
3k views

### Techniques for showing that problem is in hardness "limbo"

Given a new problem in $\mathsf{NP}$ whose true complexity is somewhere between $\mathsf{P}$ and being NP-complete, there are two methods that I know of that might be used to prove that resolving this ...
• 32.1k
3k views

### Verifying unique solutions of SAT

Consider the following problem: given a CNF formula and an assignment that satisfies this formula, is there another satisfying assignment for this formula ? What is the complexity of this problem ? (...
• 411
3k views

### Is there a natural problem on the naturals that is NP-complete?

Any natural number can be regarded as a bit sequence, so inputting a natural number is the same as inputting a 0-1 sequence, so NP-complete problems with natural inputs obviously exist. But are there ...
• 14k
5k views

### Implications of unprovability of $P\neq NP$

I was reading "Is P Versus NP Formally Independent?" but I got puzzled. It is widely believed in complexity theory that $\mathsf{P} \neq \mathsf{NP}$. My question is about what if this is ...
• 417
1k views

### "All-different hypergraph coloring" - known problem?

I am interested in the following problem: Given a set X and subsets X_1, ..., X_n of X, find a coloring of the elements of X with k colors such that the elements in each X_i are all differently ...
• 1,023
6k views

### What does 'gadget' mean in NP-hard reduction?

This question may not be technical. As a non-native speaker and a TA for algorithm class, I always wondered what gadget means in 'clause gadget' or 'variable gadget'. The dictionary says a gadget is a ...
2k views

### Do many-one reductions and Turing reductions define the same class NPC

I wonder if NPC classes defined by many-one reductions and Turing reductions are equal. Edit: Another question, are Turing reductions only collapsing C and co-C classes for some C or is there a class ...
• 1,763
5k views

### Monotone bijections between lists of intervals

I have the following problem: Input: two sets of intervals $S$ and $T$ (all endpoints are integers). Query: is there a monotone bijection $f:S \to T$? The bijection is monotone w.r.t. the set ...
• 9,269
992 views

### Is this vertex ordering optimization NP-Hard?

Could you help me to prove that the following problem is NP-hard? Problem. Given an undirected graph $G=(V,E)$, find an ordering of the nodes such that $\sum\limits_{v\in V}|succ(v)|\times|pred(v)|$ ...
• 563
372 views

• 3,264
1k views

• 201
549 views

### Complexity of the $(3,2)_s$ SAT problem?

Let define the $(3,2)_s$ SAT problem : Given $F_3$, a satisfiable 3-CNF formula, and $F_2$, a 2-CNF formula ($F_3$ and $F_2$ are defined on the same variables). Is $F_3 \wedge F_2$ satisfiable? What ...
• 1,117
768 views

• 9,448