# Questions tagged [np-complete]

The tag has no usage guidance.

138 questions
Filter by
Sorted by
Tagged with
30 views

### Bounded-Frequency Minimum Set Cover Problem

Consider the special case of the minimum set cover problem where each element of the universe occurs in at most 3 sets. Can this problem be solved in polynomial time? Is there a nontrivial upper ...
263 views

### Cook inspiration for NP completeness

An academic descendant of Cook just lectured on NP completeness. He said that the idea came from a well-known theorem in first-order logic that talks about completeness of satisfiability for ...
121 views

### For what parameters is minimum distance hard?

It has been shown by Vardy that minimum distance of a code is NP-hard (see Alexander Vardy, “The Intractability of Computing the Minimum Distance of a Code,” IEEE Trans. Inf. Thy., Vol. 43 pp. 1757--...
158 views

### Lexicographic Boolean satisfiability

Maximal Satisfying Assignment (Lexicographic Boolean satisfiability / LexMaxSAT), the problem of finding the lexicographically maximum x_1, . . . , x_n ∈ {0, 1}^n that satisfies Boolean formula φ, or ...
259 views

### Is this problem on unambiguous finite automata NP-complete?

An unambiguous finite automaton (UFA) is a nondeterministic finite automaton (NFA) such that each word has at most one accepting path. In this post, for $n\in \mathbb{N}$, what I call an $n$-UFA (resp....
408 views

### Unary language examples between L and NP

I am looking for some examples of unary languages lay between $L$ and $NP$, i.e., $L \subseteq NL \subseteq P = AL \subseteq NP$. What I found after some search(e.g., Complexity zoo for unary ...
133 views

### Is 4-Coloring restricted to graphs with crossing number 1 NP-complete?

Planar graphs are 4-colorable. Determining if a planar graph is 3-colorable is NP-Complete. A graph with a crossing number 1 (graph such that it can be drawn with $\le 1$ crossing) is 5-colorable. ...
88 views

### Choosing one number from each set so that the sum of squares of each distinct number counts is minimized

Problem is as follows: We are given $K$ subsets of $\{1,2,...,n\}$. We need to pick one number from each of these subsets such that $\sum_{i=1}^n p_i^2$ is minimized where $p_i$ is the number of times ...
72 views

368 views

### Is the maximum independent set in cubic planar graphs NP-complete?

In their famous book, Garey and Johnson, write a comment that the maximum independent set problem, in cubic planar graphs is NP-complete(page 194 of the book). They say this is by a transformation ...
886 views

### NP-complete decision problems on deterministic automata

Do you know any NP-complete decision problems on deterministic automata? Most NP-complete problems that come to my mind are either (see, or here) graph theoretical, or involve some string rewriting or ...
46 views

### Minimum rank graph cut

Consider the following problem: Input: A graph $G=(V,E)$ and a matroid $M$ on $E$, given by an independence oracle. Task: Find a cut $C\subseteq E$ in the graph, such that the rank of $C$ in the ...
118 views

### Complexity of multi-objective optimization problems

How can we define and prove the worst-case complexity of multi-objective optimization problems (MOOP)? It is easy to see that, if one of the objectives is an NP-Hard optimization problem, then the ...
61 views

### Maximum subgraph problem with unknown complexity

Let $Q$ be a polynomial time decidable graph property. In a graph let us call a subgraph $S$ a $Q$-subgraph, if $S$ has the property $Q$. Consider the following optimization problem: Maximum $Q$-...
99 views

67 views

122 views

### NP completeness of Hamiltonian cycle for the family of *dual graphs* to plane, cubic, triply connected graphs?

It is well known that the Hamiltonian cycle problem is NP-complete on the family of planar, cubic and triply connected graphs: https://epubs.siam.org/doi/abs/10.1137/0205049 For a problem I'm ...
371 views

### Error in paper "Some NP-complete geometric problems"?

The paper in question: M.R. Garey, R.L. Graham and D.S. Johnson. Some NP-complete geometric problems . This paper proofs the NP-completeness of some well-known problems, such as the Steiner Tree ...
1k views

### Password hashing using NP complete problems

Commonly used password hashing algorithms work like this today: Salt the password and feed it into a KDF. For example, using PBKDF2-HMAC-SHA1, the password hashing process is ...
129 views

### Is Prime Bounded Quadratic Congruence NP-complete?

Bounded Quadratic Congruence: Instance: Three positive integers $a$, $b$ and $c$. Question: Is there a positive integer $x<c$ such that $x^{2} \equiv a \, (mod \ b)$? Bounded Quadratic ...