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.
1,686 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
1
vote
0
answers
19
views
Hardness for COSET WEIGHT problem in terms of Hamming weight
The COSET WEIGHTS problem is given as follows paper1.
Input: A binary matrix $A\in \mathbb{F}_2^{m\times n},ドル a binary vector $y \in \mathbb{F}_2^{m},ドル and a non-negative integer $w\in \mathbb{Z}^{+}$....
3
votes
1
answer
44
views
Show that the network reliability problem is NP-complete
I am having trouble understanding the proof for why this problem is NP-complete.
"Network reliability problem"
Given an undirected graph $G,ドル we have a positive integer $T(X,Y)$ associated ...
1
vote
0
answers
12
views
Reduction from Directed Hamiltonian Path to Minimum Equivalent Graph
I am trying to reduce the Directed Hamiltonian Path Problem to the decision version of the Minimum Equivalent Graph. For instance, the Minimum Equivalent Graph is defined as follows (https://dl.acm....
1
vote
0
answers
62
views
Find a minimal binary tree that satisfies lowest common ancestor constraints
I want to find if there's a fast algorithm for the following:
Given a set of lowest common ancestor constraints, find the smallest (fewest number of nodes) strict binary tree that satisfies all of ...
0
votes
1
answer
85
views
Complexity class of an algorithm for finding the minimal elements of a partially ordered set of exponential size
I have a problem with the following specs:
The input is a permutation of size $n$.
The search space is a poset where the size could be up to $\left(\frac{n}{4}\right)!^2$ (or possibly larger, but I ...
1
vote
0
answers
60
views
Does $\mathsf{NP}$ has a $\mathsf{NC}$ verifier?
In the following quantum computing paper, there is a mention of how any $\mathsf{QMA}$ verification can be done with a logarithmic depth quantum circuit. (Claim 5.3 of this paper link.) The verbatim ...
1
vote
1
answer
75
views
Hamiltonian Path in Oriented Graph
An oriented graph is a directed graph where for each pair of vertices x,y atmost one of the directed edges (x,y), or (y,x) can exist in the graph. Is it known whether the Hamiltonian path problem on ...
1
vote
1
answer
77
views
Simple Unbounded Multi-Knapsack with Distinct Items Constraint - strongly or weakly NP-c?
Is the following Knapsack problem strongly or weakly NP-hard? We have unbounded knapsacks, meaning we can use each item unlimited number of times.
Given:
$I = \{ w_1, ... w_n \}$ - a set of the ...
2
votes
1
answer
105
views
NP-Completeness of the Rectangle Packing Puzzles
I'm reading the proof of the (strongly) NP-completeness of the Rectangle Packing Puzzles by Erik D. Demaine, Martin L. Demaine (source: https://erikdemaine.org/papers/Jigsaw_GC/paper.pdf).
...
6
votes
2
answers
845
views
Is the smallest grammar problem over the singleton alphabet known to be NP-complete or ...?
I can't find straight answer on this via googling around. Can you provide a reference?
The smallest grammar problem over a singleton alphabet is to find the smallest CFG $g$ that produces one and ...
0
votes
1
answer
179
views
Does a Polynomial-Time Algorithm for Graph Coloring Problem proves P = NP?
Recently, I came across a video introducing an algorithm (GAF) that computes the chromatic number of any connected, undirected graph in polynomial time.
So, what impact it has on P = NP?
4
votes
1
answer
225
views
NP-completeness of a variation of the vertex coloring problem
I've encountered the following coloring problem: Suppose we have a complete graph with $n$ vertices, with each edge colored 0/1. We need to assign a 0/1 color to each vertex, too, such that the ...
1
vote
1
answer
87
views
3-NAE-SAT to 1in3-SAT Reduction
can someone help with 3-NAE-SAT to 1in3-SAT reduction.
3-NAE-SAT:Each clause contains 3 literals. At least 1 literal must be TRUE and at least 1 literal FALSE.
1-in-3-SAT: Each clause contains 3 ...
0
votes
0
answers
55
views
If NP=P, what will happen to this planet? [duplicate]
I know that our modern IT infrastructure is based on the assuption that NP!=P, e.g. cryptocurrency, public key cryptography. But if(only if), if NP=P, someone at sometime find that one algorithm could ...
2
votes
0
answers
53
views
Asymptotic complexity of knapsack algorithm considering all numbers ∈ Z
In the knapsack problem, we consider numbers ∈ Z+ which gives us a run time of $O(nW)$. To my understanding, this is pseudo-polynomial and the worse case runtime is $O(n*2^{log(w)})$
My question is, ...