# Questions tagged [np-complete]

The tag has no usage guidance.

176 questions
Filter by
Sorted by
Tagged with
21 views

• 544
113 views

### Constrained Bipartite Matching

Let $G = (X,Y,E)$ be a bipartite graph. For some $A \subseteq X$ we say that $A$ can be perfectly matched if there is a matching $M \subseteq E$ such that all vertices in $A$ are matched; that is, for ...
• 412
101 views

121 views

### Does NP Completeness always fall on one side or the other of an intermediate computation?

Let $L$ be an NP complete language. My loose intuition for completeness suggests that, at any point in a computation tableau for $L$, either the computation has "already done an NP complete ...
• 2,481
163 views

### Short UNSAT Certificates for X3SAT

Exactly 1 in 3 SAT ($X3SAT$) is a variation of the Boolean Satisfiability problem. Given an instance of clauses where each clause has three literals, is there a set of literals such that each clause ...
60 views

### Relativized Version of NP^A-complete

I was reading this post about whether Cook-Levin relativizes and at the bottom of the answer, they include a quote from Computational Complexity by C. Papadimitriou (this is a longer version of the ...
292 views

### Is the following equitable factoring problem $NP$-hard or in $P$?

Consider the following factoring problem: Given an integer $r$ and another integer $N$ along with all of its $n$ number of prime factors and their corresponding multiplicities $\{p_i,e_i\}_{i=1}^n$, ...
• 13.1k
166 views

### Is the weighted sum of subset prefix product problem NP-hard?

I have this strange problem where we have a set of positive numbers $M$, a fixed number $n$, and a function $f: M \rightarrow R^+$ mapping each number in M to another positive number. We want to know ...
301 views

### Hardness assumption: an NP-complete problem whose ratio of hard instances do not tend to zero?

I am wondering about the following property $\text{(P)}$ of an $NP$-complete language $L$ \begin{align}\exists M\text{ a polytime machine}\lim_{n\to\infty}P(\text{M solves a random instance of size...
• 153
1 vote
57 views

### Partition of multisets of polynomials

Problem: Given a multiset S of irreducible polynomials in Z[x], say YES if S can be partitioned into two nonempty multisets A and B such that both the product of all the elements of A and the product ...
• 61
1 vote
301 views

### How to show that Color Tiles is NP-Complete

Color Tiles is a puzzle game where color tiles are laid out in a rectangular grid. A tile is visible to an empty grid cells if there is a clear line-of-sight in one of the 4 cardinal directions (You ...
317 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 ...
• 1,049
232 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 ...
456 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....
• 1,431
673 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 ...
• 3,707
155 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. ...
1 vote
91 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 ...
• 113
1 vote
79 views

848 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 ...
• 3,440