# Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

569 questions
Filter by
Sorted by
Tagged with
582 views

### Does solving matrix multiplication in quadratic time imply that SETH is false?

I have a little conjecture that if you could perform matrix multiplication (or solve 3-clique) in $O(n^2 \log(n))$ time, then you could solve CNF-SAT in $O(2^{(1-\epsilon)n})$ time. In other words, ...
974 views

### Phase Transitions in NP Hard Problems

SAT Problems have a phase transition that depends on the ratio $r$ of variables to clauses. Below $r$, SAT problems are solvable quickly; above, they become difficult. The same is true of NP ...
507 views

### Problems with complexity between P and NP that have NP-complete generalizations

Can anyone list some well-known problems that satisfies the following conditions: ...
1k views

### Classes of graphs with easy Hamiltonian cycle but NP-hard TSP

The Hamiltonian Cycle Problem (HC) consists in finding a cycle that goes through all vertices in a given undirected graph. The Travelling Salesman Problem (TSP) consists in finding a cycle that goes ...
522 views

### Can we fast generate perfectly uniformly mod 3 or solve NP problem?

To be honest, I don't know that much about how random number are generated (comments are welcome!) but let's assume the following theoretical model: We can get integers uniformly random from $[1,2^n]$ ...
2k views

### Is the half-filled magic square problem NP-complete?

Here is the problem: We have a square with some numbers from 1..N in some cells. It's needed to determine if it can be completed to a magic square. Examples: ...
867 views

### Finding the sparsest solution to a system of linear equations

How hard is it to find the sparsest solution to a system of linear equations? More formally, consider the following decision problem: Instance: A system of linear equations with integer coefficients ...
566 views

### Are there interesting graph classes where the treewidth is hard (easy) to compute?

Treewith is an important graph parameter that indicates how close a graph is from being a tree (although not in a strict topological sense). It is well known that computing the treewidth is NP-hard. ...
3k views

### Lexicographically minimal topological sort of a labeled DAG

Consider the problem where we are given as input a directed acyclic graph $G = (V, E)$, a labeling function $\lambda$ from $V$ to some set $L$ with a total order $<_L$ (e.g., the integers), and ...
250 views

980 views

### Reducing P vs. NP to SAT

The following question uses ideas from cryptography applied to complexity theory. That said, it is a purely complexity-theoretic question, and no crypto knowledge whatsoever is required to answer it. ...
1k views

### Directed NP-hard problems on DAGs

Tree width measures how close a graph is to a tree. Several NP-hard problems are tractable on graphs with bounded tree width. If a problem remains NP-hard on trees then tree width cannot save us. This ...
3k views

### How hard is binary Sudoku puzzle?

Sudoku is a well-known puzzle that is NP-complete. Binary Sudoku is a variant that only allows the numbers $0$ and $1$. The rules are as follows. Each row and each column must contain an equal number ...
1k views

120 views

### NP-Hardness of 4-cycle packing problem in complete bipartite digraph?

A directed complete bipartite graph is a bipartite graph where there is exactly one directed edge between any two vertices from its two different parts. In other words, it's an orientation of 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 ...
787 views