# 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 '.

100
questions

**0**

votes

**0**answers

48 views

### Computational practicality of proving a theorem by transforming into a map coloring and finding $P(3)$, where $P$ is the chromatic polynomial

So I have heard that you can transform a math statement into a map in such a way that proving the statement is true is equivalent to finding a $3$-coloring of that map.
I'm also aware that you can ...

**1**

vote

**1**answer

164 views

### Is there an example of converting a mathematical statement into a three color mapping? [closed]

https://youtu.be/5ovdoxnfFVc?t=1118
At this point, prof Wigderson says it is easy to go from a mathematical statement to a graph coloring problem. The video does not provide an example of this, and a ...

**1**

vote

**0**answers

30 views

### Finding valuable conjectures from NP-Complete problems [closed]

Let's suppose we've got an NP-Complete problem, such as the subset sum problem. There are conjectures that, if proven true, would place the subset sum problem to the P-Complete problem realm?
If the ...

**-1**

votes

**3**answers

106 views

### Are <sum, product, N> triplets unique and hard to solve? [closed]

This question comes from some reasoning I made myself about a "joke block chain" where every new block is labeled with a triplet <S, P, N> where where S = sum of the N transactions so ...

**11**

votes

**1**answer

767 views

### How did the Baker-Gill-Solovay paper come to be?

How did the Baker-Gill-Solovay paper come to be? Why were those three people talking together about "Relativizations of the $P=?NP$" question, and what was their collaboration like for the ...

**2**

votes

**2**answers

140 views

### Transforming an optimization problem to maxmin formulation

Given $N=mn$ real numbers $a_i$, we seek to partition them into $n$ subsets $S_j$ ($1\le j\le n$), each containing $m$ numbers, so as to maximize $\prod_{j=1}^n \sum_{a_i\in S_j} a_i$. My questions ...

**2**

votes

**1**answer

157 views

### What is the efficiency of this algorithm which decides the answer to the Boolean satisfiability problem? [closed]

I have just written a short javascript program which, given any boolean expression with $N$ variables, completes in N "ticks" of the clock and which makes the decision. I will explain this algorithm, ...

**3**

votes

**0**answers

99 views

### Is the Weber problem a NP-hard problem?

The Weber problem is a special case of a facilities location problem : In a basic formulation, the facility location problem consists of a set of potential facility sites L where a facility can be ...

**0**

votes

**1**answer

157 views

### Is it theoretically possible to find a factoring algorithm that runs in polynomial time? [closed]

Given that we don't know if P=NP, what's to stop someone from finding tomorrow an algorithm that makes prime factoring, or any other trap-door function reversing for that matter, computationally ...

**2**

votes

**0**answers

45 views

### Proof for the NP-hardness of the Max-3-DCC Problem

The Max-3-DCC is the variant of vertex cycle cover problem where each of the vertex disjoint oriented cycles consists of at least 3 arcs and every vertex belongs to exactly one of those cycles; ...

**1**

vote

**0**answers

39 views

### Determining the minimum weight maximal oriented subgraph of a complete directed graph

Let $G(V,A,W):\ |V| = n,\ A=V\times V\setminus \lbrace (v,\ v)\rbrace,\ W\in\mathbb{R}_+^{n\times n},\ W^T\ne W $ be a complete directed graph with asymmetric weights.
Questions:
What is the ...

**1**

vote

**0**answers

115 views

### Is bounded graph isomorphism $NP$ complete?

Fix a matrix $M\in(\mathbb Z\backslash\{0\})^{n\times n}$ where $\|M\|_\infty\leq 2^{poly(n)}$.
Is the bounded graph isomorphism problem
Given symmetric $A,B\in\{0,1\}^{n\times n}$ and $U,V>0$ ...

**12**

votes

**5**answers

995 views

### Equivalent forms of the P vs. NP problem

Many things in math can be formulated quite differently; see the list of statements equivalent to RH here, for example, with RH formulated as a bound on lcm of consecutive integers, as an integral ...

**2**

votes

**0**answers

60 views

### NP - hardness of school scheduling problem with a restriction

I do have a real-life scheduling problem for a special education school.
Basically, i have a binary variable containing teachers, subject, time slot and rooms as indices.
The goal is to assign each ...

**16**

votes

**2**answers

498 views

### Is this kind of “Gerrymandering” NP-complete?

[I posted this on Math Stack Exchange about two weeks ago, but didn't get any reply, so I'm trying it here.]
Consider the following simplified form of "Gerrymandering": You have $n^2$ ...

**1**

vote

**0**answers

51 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**

vote

**0**answers

121 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?

**3**

votes

**0**answers

47 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$-...

**3**

votes

**0**answers

103 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 ...

**1**

vote

**0**answers

75 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

**1**

vote

**0**answers

70 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, ...

**12**

votes

**2**answers

399 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 ...

**15**

votes

**3**answers

641 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 ...

**3**

votes

**2**answers

175 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 ...

**16**

votes

**2**answers

520 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 ...

**1**

vote

**0**answers

46 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 ...

**0**

votes

**1**answer

215 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 ...

**3**

votes

**1**answer

260 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 ...

**11**

votes

**3**answers

1k 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 (...

**0**

votes

**1**answer

117 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 ...

**4**

votes

**1**answer

677 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. ...

**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. ...

**3**

votes

**1**answer

128 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 ...

**2**

votes

**1**answer

99 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

161 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 ...

**2**

votes

**2**answers

325 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 ...

**2**

votes

**1**answer

199 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}$, ...

**1**

vote

**0**answers

23 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 $...

**-1**

votes

**2**answers

488 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?

**3**

votes

**1**answer

177 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 \...

**2**

votes

**1**answer

250 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 ...

**2**

votes

**0**answers

138 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**

votes

**1**answer

166 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?

**0**

votes

**0**answers

96 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

346 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 ...

**3**

votes

**1**answer

293 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 ...

**4**

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 ...

**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

618 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$ ...

**2**

votes

**1**answer

165 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?