Questions tagged [np-complete]

Questions about the hardest problems in NP, i.e. of those that can be solved in polynomial time by nondeterministic Turing machines.

171 questions
Filter by
Sorted by
Tagged with
4k views

Prove Partition is NP-Complete using that SubsetSum so is it

The SubsetSum problem decides whether a set $S = \{s_1, s_2,..., s_n\}$ and $k \in \mathbb{N}_0$ contains a subset of $S$ such that its summation is $k$ or not. This problem is NP-Complete. The ...
327 views

Is this problem NP-hard? select k sets from a collection of sets such that each selected set has an empty intersection with the non selected ones

select k sets from a collection of sets such that each selected set has an empty intersection with the non selected ones
1k views

295 views

Sudoku Puzzles in O log n time although inefficient

Suppose, I got a hypothetical fixed list of all possible general Sudoku puzzles. I then create the pseudo-code to demonstrate the algorithm. The algorithm does a search to compare the indexes of ...
654 views

Which of the following problems can be reduced to the Hamiltonian path problem?

I'm taking the Algorithms: Design and Analysis II class, one of the questions asks: Assume that P ā  NP. Consider undirected graphs with nonnegative edge lengths. Which of the following problems ...
122 views

145 views

Saxe's proof of 1-embeddability

I've been reading Saxe's proof that 1-embeddability of integer weighted graphs is NP-Complete (http://www.math.columbia.edu/~dpt/RigidityREU/Saxe79EmbedNPHard.pdf Theorem 3.2). I don't understand how ...
1k views

If A is polynomial time reducible to B does that imply not(A) is polynomial reducible to not(B)

$A\leq_p B \iff \bar{A}\leq_p \bar{B}$ (if A is polynomial time reducible to B does that imply that complement of A is polynomial reducible to complement of B) I was told that this is the case based ...
68 views

Partitioning in time complexity of the sum

We all know the partitioning problem: Given a super-set S of integers, can we partition S into 2 subsets with the same sum. And of course this problem is NP-complete. My question is - let's denote M ...
184 views

Quadratic Diophantine equation - Polynomial Time Cases

In number theory, solving a Quadratic Diophantine equation (a, b, c constants) $$a*x^2+b*y= c$$ is an NP-Complete problem. Even for a=1, the problem remains NP-Complete. The solution (x, y) are ...
346 views

NP-complete promise problems? [closed]

Are there any good examples of promise problems that are NP complete?
38 views

Karp hardness of an equidistant set in digraph

Following the success of the undirected version: Karp hardness of an equidistant vertex set Inspired by the success of this long ago question: NP-hardness of problem with indices and subsets We ...
191 views

NP hardness of unique Puzzle Generation

Introduction For those who did not read my prior question, I have created an algorithm that generates n^2 x n^2 Sudoku Grids. Out of those grids I remove elements to give only one solution. The ...