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

Filter by
Sorted by
Tagged with
2
votes
2answers
136 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
1answer
142 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
0answers
71 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
0answers
62 views

A variant of weighted set cover problem

I came across a paper that proves a generalized version of the weighted set cover problem is NP-complete. The problem is stated as follows: Given a collection of $n$ elements, a collection of ...
0
votes
0answers
39 views

Effect of uniqueness of optimal solution on difficulty of np-hard optimization problems

Question: is it harder to find an optimal solution of an NP-hard optimization problem by exact deterministic algorithms if the optimal solution isn't unique or do multiple optimal solutions lead to ...
0
votes
1answer
145 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
0answers
43 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; ...
0
votes
0answers
34 views

Transformation of asymmetric traveling salesman problems into Chinese postman problems

I have found transformations of Chinese Postman Problems (CPPs) into Asymmetric Traveling Salesman Problems (ATSPs), but didn't find anything about transformations in the opposite direction. Having ...
1
vote
0answers
34 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 ...
1
vote
0answers
111 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$ ...
11
votes
5answers
843 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
0answers
58 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 ...
9
votes
1answer
260 views

Is this kind of “Gerrymandering” NP-complete?

[I posted this on math.stackexchange.com 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$ squares ...
1
vote
0answers
48 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
0answers
114 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
0answers
46 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 ...
3
votes
0answers
102 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
0answers
68 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
0answers
69 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, ...
10
votes
2answers
346 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
3answers
610 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
2answers
170 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
2answers
501 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
0answers
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
1answer
205 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
1answer
254 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
3answers
852 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
1answer
114 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 ...
3
votes
1answer
578 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
3answers
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
1answer
125 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
1answer
95 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
0answers
160 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
2answers
265 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
1answer
193 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
0answers
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
2answers
426 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
1answer
175 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
1answer
245 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
0answers
137 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
1answer
165 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
0answers
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
2answers
336 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
1answer
276 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 ...
3
votes
2answers
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 ...
7
votes
4answers
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
1answer
432 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$ ...
3
votes
1answer
164 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?
4
votes
1answer
900 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--...
9
votes
3answers
547 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 ...