Questions tagged [np]
In computational complexity, NP is the complexity class consisting of problems whose yes instances can be verified in polynomial time. NP stands for 'nondeterministic polynomial time '.
135 questions
1
vote
0
answers
70
views
Shortest Lattice Vector with restricted $x$
Let $\Lambda$ be a lattice with basis, $B$ consisting of vectors $b_i$, so that the elements of $\Lambda$ are of form, $y\in \Lambda \iff y=Bx=\sum_i b_ix_i$ for some $x_i\in\mathbb{Z}$.
My questions ...
- 1,096
1
vote
0
answers
207
views
Is it known whether $\mathrm{NP \subseteq P/poly}$?
It is not immediately clear to me whether this statement is true or false. Can finite restrictions of NP problems be computed in polynomial time?
- 11
3
votes
0
answers
56
views
Karp hardness of two cycles which lengths differ by one
Our problem is as follows:
NEARLY-EQUAL-CYCLE-PAIR
Input: An undirected graph $G(V,E)$
Output: YES if there exists $2$ (simple) cycles in $G$ which lengths differ by $1$, otherwise NO
Is it $NP$-...
- 121
3
votes
0
answers
165
views
$\mathrm{NP}$-complete problems in graph theory: undirected vs. directed
Is it true that it is much easier to establish $\mathrm{NP}$-complete on undirected graphs than digraphs (directed graph)?
Academic articles proving $\mathrm{NP}$-completeness of problems on ...
user128192
1
vote
0
answers
103
views
descriptive complexity theory to attack computational complexity problems [closed]
What is the usefulness of descriptive complexity to attack computational complexity theory?what are the recent results in this direction? Thanks
- 11
1
vote
0
answers
78
views
Bipartite clustering is NP-hard?
Let $G = (A\cup B, E)$ be a bipartite graph with edge weights $w: E\to \mathbb{R}$. Find a partition $B_1, B_2$ of $B$ and a nonempty disjoint subsets $A_1, A_2$ of $A$ such that $w(A_1,B_1) + w(A_2, ...
- 221
12
votes
2
answers
423
views
Techniques for proving relaxed one-wayness of functions
Existence of one-way functions is a widely accepted conjecture in complexity theory. A function is one-way if it is computable in polynomial-time but not invertible in polynomial-time (this is ...
- 2,993
16
votes
4
answers
1k
views
Representing mathematical statements as SAT instances
The following problem (call it THEOREMS) belongs to class NP.
Input: Mathematical statement $S$ (written in some formal system such as ZFC) and positive integer $n$ written in unary.
Output: "Yes" if ...
- 781
3
votes
2
answers
208
views
(How) do Better TSP Heuristics help in Answering the $NP=P$ Question?
This question is motivated by my impression, that finding better heuristics for the TSP problem (or any other $NP$-complete problem) is "only" of practical interest, but doesn't provide any progress ...
- 13.2k
16
votes
2
answers
603
views
NP-hardness of finding 0-1 vector to maximize rows of {-1, +1} matrix
Consider the following discrete optimization problem: given a collection of $m$-dimensional vectors $\{ v_1, \dots, v_n \}$ with entries in $\{-1, +1\}$, find an $m$-dimensional vector $x$ with ...
- 163
1
vote
0
answers
49
views
Cost associated set problem NP-hard
I have the following problem. I wonder whether or not it appears in the literature. Is it NP-hard?
Given a set $S = \{1,2,\ldots,m\}$, and $A_1,\ldots, A_n$ are subsets of $S$. Each set $A_i$ has ...
- 221
1
vote
1
answer
347
views
Finding a subgraph of cliques with the minimum total sum weight
Consider the following graph problem. For a number $K$ and a set $\mathcal{K} = \{ 1, \ldots,K\}$, we have a set of vertices $V_k^s$ for all $s \subset \mathcal{K} \setminus \{k\}$, $s$ is not empty ...
- 113
3
votes
1
answer
334
views
Simple cake cutting puzzle
I got interested in a cake cutting problem from computational perspective. Suppose we have a piece of cake and we want to slice it into pieces using several cuts (straight lines). Each cut represents ...
- 2,993
11
votes
3
answers
2k
views
Is there a polynomial-time algorithm for untangling the unknot?
I've found assertions that recognising the unknot is NP (but not explicitly NP hard or NP complete). I've found hints that people are looking for untangling algorithms that run in polynomial time (...
- 161
0
votes
1
answer
128
views
Continuous backpack with multiple choice items. NP prove
Continuous backpack with multiple choice items is the problem where you need to collect items by one from each of distinct sets and associate them with rational numbers so that their sum of weights ...
- 1
4
votes
1
answer
1k
views
What arguments do exist against defining completeness in NP using injective Karp reductions?
It is crucial to use the right notion of reduction to define completeness inside NP. Different notions of completeness inside NP may have significant impact on the properties of complete languages. ...
- 2,993
7
votes
3
answers
1k
views
How slow are direct solutions of NP-complete problems on computers?
Sometimes I see that people call a problem NP-hard and because of that refuse to create computer algorithms that directly solve it. I think I've never read actual benchmark results for such problems. ...
- 171
3
votes
1
answer
147
views
Covering a graph by trees with depth constraint
Given a graph $G$ and a depth constraint $h$, my question is: what is the complexity to find a tree cover of $G$, denoted as $T=\{T_1, T_2, ..., T_n\}$. For each $T_i$, its depth(height) is no larger ...
- 31
2
votes
1
answer
201
views
Minimum cover for sets in which each element appears in exactly 2 sets?
Is there an algorithm for finding minimal covers of a set of sets in which each element of the universe appears in exactly 2 sets? I realize that LP relaxation approximates this to within a factor of ...
1
vote
0
answers
167
views
How I can prove the equality $P^{P_{\operatorname{space}}}=NP^{P_{\operatorname{space}}}=P_{\operatorname{space}}^{P_{\operatorname{space}}}$ [closed]
I know how to prove that if $A \in P^{P_{\operatorname{space}}}$ then $A \in NP^{P_{\operatorname{space}}}$ and $A \in P_{\operatorname{space}}^{P_{\operatorname{space}}}$.
I don't know how to prove ...
- 119
2
votes
2
answers
450
views
How to complete the NP-hardness proof of GENERAL-SQUARE-PRODUCT?
I am interested in the complexity of the following problem:
GENERAL-SQUARE-PRODUCT
INSTANCE: Two sets $A=\{a_1,\ldots,a_n\}$ and $B=\{b_1,\ldots,b_n\}$ of integers, a positive integer $k<n$ and a ...
- 161
2
votes
1
answer
223
views
Minimal Support Solutions of a Linear System (Dissertation)
For a given $n \times m$ matrix A with $m>>n$ and a given vector $\vec b \in \mathbb{F}^{n \times 1}$, and given that $A\vec{x}=\vec{b}$ for at least one $\vec{x} \in \mathbb{F}^{m \times 1}$, ...
- 259
1
vote
0
answers
28
views
The complexity of Max-K interval selection
I came up with the following problem, but do not know how to analyze it.
Let $S$ be an ordered set of integers with size $n$ (i.e., $S=\{1,2,...,n\}$). An interval $INV(a,b)$ covers the elements in $...
- 11
-1
votes
2
answers
775
views
Is finding a local minimizer of a NP-hard optimization problem is still NP-hard [closed]
I was wondering if for a NP-hard optimization problem, I only want to find its local minimizer, is it still NP-hard or NP-hard is only true when trying to find a global minimizer?
- 11
3
votes
1
answer
258
views
Can we say that this problem is NP-hard?
I have an optimization problem of the form:
\begin{align}
&\text{maximize}\quad f(\mathbf{x}) = \dfrac{\sum\limits_{n=1}^{N}x_na_n}{1+\sum\limits_{n=1}^{N}x_nb_n}\\
& \text{subject to}\quad \...
- 161
2
votes
2
answers
461
views
On Knot Equivalence problem statement
How is the knot equivalence problem represented?
By this I mean I am looking for an analogy that compares with graph equivalence. For graph equivalence, we have two graphs $G_1$ and $G_2$ with ...
- 13.9k
2
votes
0
answers
151
views
How hard is recognizing a permutation that is a square for the shift product?
This is a continuation of my attempts to generate simple combinatorial computational problems that turn out to be computationally hard (NP-complete). In this pursuit, I came up with a permutation ...
- 2,993
3
votes
1
answer
214
views
NP-hardness of finding maximum of minimum element in diagonal of a matrix
For $A = \{a_{ij}\} \in R^{n\times n}$, is finding
$$
\max_{\sigma \in S_n}\min_{1 \le i \le n} a_{i,\ \sigma_i}
$$
NP-hard?
- 163
0
votes
0
answers
104
views
Surd Partition Problem
Could the following "Surd Partition" problem be NP complete? Note that if the square roots are omitted in the following then the problem is well known to have a polynomial solution.
Surd Partition
...
8
votes
2
answers
476
views
Is this problem on weighted bipartite graph solvable in polynomial time or it is NP-Complete
I encounter this problem recently and I want to know whether it is NP-Complete or solvable in polynomial time:
Given a undirected weighted bipartite graph $G = (V, E)$ where $V$ can be partitioned ...
- 377
3
votes
1
answer
408
views
reduction to np hard ordering problem
I am trying to show a reduction from a problem of ordering problem to an np-hard problem that has approximation poly-time algorithm.
My problem is: I have M auctions and in each auction I have N ...
- 31
7
votes
2
answers
2k
views
What impact would P=BQP have on NP?
Assuming P=BQP (ie we have polynomial time algorithms to solve all BQP problems) can we use it to prove that P=NP?
The argument is that since we have the Grover's algorithm which can solve NP ...
- 81
8
votes
4
answers
2k
views
NP-hard problems in linear algebra and real analysis [closed]
I am curious about NP-hard problems in linear algebra and real analysis. An example in linear algebra would be the calculation of the permanent.
I would thus like to collect in this thread a list of ...
2
votes
1
answer
976
views
Is undirected short-simple-path-through-3-vertices decidable in polynomial time?
Consider the following language:
$L=\{\langle G=(V,E),s,v,t,l\rangle\;|\;s,v,t\in V, l\in \mathbb{N} \wedge $ There exists a simple path from $s$ to $t$, going through $v$ of length $\leq l\}$.
($G$ ...
- 618
2
votes
1
answer
183
views
Is the domination number NP for non-bipartite graphs?
Calculating the domination number is an NP-Hard problem. Does it remain NP-Hard if we restrict it to non-bipartite graphs?
- 6,962
5
votes
1
answer
1k
views
Simple example of why Differential Equations can be NP Hard [closed]
Just looking for a simple example of why Differential Equations can be NP hard
Edit:
It appears that the answer below may be what I was looking for, but I am clarifying just in case:
Slides 58--...
- 159
9
votes
3
answers
846
views
Conjecture on NP-completeness of tesselation of Wang Tile up to finite size
Motivated by these following questions on tessellation:
coloring in lattice
Reference for Wang Tile
Computational approach deciding whether a set of Wang Tile could tile the space up to some size
...
user46976
0
votes
1
answer
2k
views
How to determine the distance between two matrices under the meaning of a matrix function? [closed]
Suppose a nonlinear infinitely continous differentiable function $f:\mathbb{D}\mapsto \mathbb{R^+}$, where $\mathbb{D}\subset\left\{X|\text{rank}{X}=2,X\in\mathbb{R}^{3\times 3}\right\}$ is a ...
- 197
3
votes
0
answers
260
views
Partitioning a cubic graph into two induced cycles of equal order
I am aware that deciding the existence of a partition of the vertices of a connected graph $G(V, E)$ into two induced cycles is $NP$-complete(Theorem 2). Induced cycle is a cycle without any chord (...
- 2,993
2
votes
3
answers
184
views
Reference Request for: Finding Large Bipartite Subgraphs via Destruction of Odd Cycles in Graphs
From the observation, that a bipartite graph doesn't contain odd cycles, it would seem natural to attempt to destroy all odd cycles in the most efficient way, by either removing edges or vertices of ...
- 13.2k
35
votes
1
answer
2k
views
How hard is reconstructing a permutation from its differences sequence?
My interest in combinatorially motivated computational problems led me to search for simple problems that turn out to be computationally hard. In this pursuit, I came up with a problem which I hope is ...
- 2,993
3
votes
0
answers
244
views
Intermediate $\mathsf{NP}$-complete problems?
Partition problem is weakly NP-complete since it has polynomial (pseudo-polynomial) time algorithm if input integers are bounded by some polynomial. However, 3-Partition problem is strongly NP-...
- 2,993
10
votes
0
answers
327
views
Testing contrasts in statistics: Is this provably a hard problem, or not?
Scheffé's method for identifying statistically significant contrasts is widely known. A contrast among the means $\mu_i$, $i=1,\ldots,r$ of $r$ populations is a linear combination $\sum_{i=1}^r c_i \...
1
vote
3
answers
267
views
Strategic vertex labeling
We are given a graph $G=(V,E)$ with positive edge weights $w_{i}$ and numerical {0,1,-1} labels $l$ for all vertices . We know that $G$ has a subset $G'$ with all vertices labeled 0(all vertices with ...
- 113
1
vote
0
answers
145
views
Are set covering problems with nonlinear cost functions NP-Hard?
Are set covering problems (set cover problem wikipedia) with a nonlinear cost function also NP-hard? Is there a general result about this?
To be more specific the cost function I am interested in ...
0
votes
2
answers
913
views
Generating 3SAT circuit for Integer factorization example
I read somewhere that 3SAT can be used to solve Integer Factorization.
If that is true, could someone teach me a simple example of generating the 3SAT by using a small number? Let's say you are given ...
- 3
1
vote
0
answers
143
views
Non-trivial lower bound on the number of "Graph Diagonals"
The definition of Graph Diagonals, that are the subject of this question, is based on the notions of crossing edges and on connected graphs:
Two edges $AC$ and $BD$ of a complete, symmetric and ...
- 13.2k
5
votes
0
answers
139
views
Are there sampNP-intermediate problems?
This questions is approximately cross-posted from theoretical computer science stackexchange
Ladner's theorem establishes that if $\mathsf{P} \ne \mathsf{NP}$ then $\mathsf{NPI} := \mathsf{NP} \...
- 1,368
18
votes
7
answers
3k
views
SAT and Arithmetic Geometry
This is an agglomeration of several questions, linked by a single observation: SAT is equivalent to determining the existence of roots for a system of polynomial equations over $\mathbb{F}_2$ (note ...
- 1,368
0
votes
1
answer
148
views
A simplified/harder 2-sequence longest common sub-sequence (LCS) problem
Basically, its a 2-sequence longest common sub-sequence (LCS) problem.
What's so special?
1: each alphabet only occurs 2 times, one in each sequence, which means with no same alphabet in one ...
