The np tag has no wiki summary.

**8**

votes

**2**answers

187 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

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

**2**

votes

**2**answers

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

**6**

votes

**4**answers

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

**1**

vote

**1**answer

85 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

**1**answer

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

**1**

vote

**1**answer

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

**9**

votes

**3**answers

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

**0**

votes

**1**answer

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

**3**

votes

**0**answers

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

votes

**3**answers

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

**26**

votes

**1**answer

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

votes

**0**answers

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

**9**

votes

**0**answers

218 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

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

**1**

vote

**0**answers

77 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

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

**1**

vote

**0**answers

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

**5**

votes

**0**answers

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

**12**

votes

**6**answers

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

**0**

votes

**1**answer

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

**7**

votes

**1**answer

215 views

### one-dimensional (sort of) tilings

Consider the following one-dimensional tiling problem. Each "tile" is a sequence of nonnegative integers. A "region" is also such a sequence. I can shift the "tiles", or reverse them. A tiling is ...

**1**

vote

**1**answer

235 views

### Need input on a potentially NP-hard maximal edge-weighted multi-cycle graph

I've posted a question on Stack Overflow regarding a seemingly NP-hard problem on maximization of weighted cycles in a graph problem.
One of the respondents cited Professor David Speyer's Math ...

**6**

votes

**0**answers

513 views

### Is Logical Min-Cut Problem, NP-Complete?

Logical Min Cut (LMC) Problem: Suppose that G = (V, E) is an unweighted digraph, s,t are two vertices of V, and t is reachable from s. LMC Problem states that how we can make t unreachable from s by ...

**2**

votes

**1**answer

484 views

### #P version of SUBSET SUM

The decision version of the SUBSET SUM problem asks the following: Given a set of integers $S =$ {$a_1, ..., a_n$}, is there a subset $S'$ of $S$ such that the sum of the elements in $S'$ is equal to ...

**3**

votes

**0**answers

697 views

### 0,1 solution to system of linear integer equations.

I have the following problem:
$A x = b$
where $A, b$ - $m \times n$-maxtrix and $m$-vector of nonnegative intgers (respectivelly).
$x \in \{0,1\}^n $ - vector of binary variables, which need to be ...

**6**

votes

**1**answer

648 views

### NP-hardness of a graph partition problem?

I'm interested in this problem: Given an undirected graph $G(E, V)$, Is there a partition of $G$ into graphs $G_1(E_1, V_1)$ and $G_2(E_2, V_2)$ such that $G_1$ and $G_2$ are isomorphic? Here $E$ is ...

**5**

votes

**0**answers

232 views

### Any approximation algorithms for self-avoiding walks?

I've a graph whose edges are weighted by probabilities, perhaps all equal. I would like to compute the overall probability of traveling between vertices x and y in the graph after I delete each edge ...

**0**

votes

**0**answers

283 views

### Is this minimization problem NP-Complete ?

We are given an nx(n+k) matrix A, with entries in GF(2), of the form A=(In|B) where In is a nxn identity matrix where the matrix B has no "zero" rows or columns.
The problem is to partition the ...

**0**

votes

**1**answer

550 views

### Knapsack Problem Specifics [closed]

(i) Are there limits on how many numbers must be in the set? { 1, 2 } or { 1, 5, 7, 8 , 9}
(ii) Are there limitations on how diverse or similar the numbers in the set can be? Coprime? Pairwise? { 1, ...

**2**

votes

**2**answers

530 views

### Could this be a NP complete?

Given a undirected and unweighted graph G(V,E). M is a subset of vertices of V.
s is a vertex in V - M.
Find an optimal tree T of G defined as:
(1) M and s are in V(T)
(2) Distance (which is ...

**2**

votes

**2**answers

177 views

### how to find vertex of parallelotope closest to given point P in R^n ? (Or minimize quadratic form over {+-1}) Is it NP ?

Consider a parallelotope in R^n and some point "P" in R^n.
What algorithms (except of brute force) can be suggested to find the closest vertex of paralleloptope to "P" ?
Is it NP ?
Parallelotope ...

**4**

votes

**1**answer

1k views

### Closest vector problem (=nearest lattice point) is trivial for “reduced lattice” ?

Consider some lattice in R^n. Take some point "P" in R^n (which does not belong to this lattice in general). The problem is to find "nearest" lattice point. The problem is known NP-hard in general it ...

**7**

votes

**2**answers

1k views

### How to find nearest lattice point to given point in R^n ? Is it NP ?

Consider some lattice in R^n.
Take some point "P" in R^n (which does not belong to this lattice in general).
What are the algorithms to find some nearest lattice point to "P" ?
"Nearest" - means in ...

**5**

votes

**1**answer

836 views

### Is pattern recognition NP-complete?

Hello,
is the problem of pattern recognition (for a given sequence of n numbers, find the shortest Turing machine with an alphabet of 42 elements that will output these n numbers in, say, 5*n^3 time) ...

**4**

votes

**4**answers

619 views

### how to find vector $(\pm 1, \pm 1, \pm 1, … \pm 1)$ which is most close to given vector (r_1,…r_l) ? Is it NP-problem ? What algorithms are available ?

Given:
some vector $R=(r_1...r_l)$ - real numbers,
and a set of distinct vectors with $+1$ or $-1$ coordinates
$$\begin{array}{c} V_1=(c_{1,1} ... c_{1,l}),\\\
V_2=(c_{2,1} ... c_{2,l}),\\\
...

**0**

votes

**1**answer

525 views

### A few questions about Computational Problems Complexity Classification

(This might look like just a post to you and you might think I shouldn't have submitted it as a question here but in reality it is some questions put together, so I hope you don't close it)
I only ...

**2**

votes

**0**answers

236 views

### Complexity of a variant of the Mandelbrot set decision problem?

This is a modified version of a question posted on StackExchange TCS.
Mandelbrot set is defined using the complex equation $P_c (z)=z^2 +c$ where $c$ is a complex number. Let us define
...

**1**

vote

**0**answers

214 views

### Self-improvement property of optimazation problems?

Maximum CLIQUE problem is very hard to approximate. It has a self-improvement property defined using graph product which is utilized to prove hardness of approximation results. One such example is ...

**2**

votes

**0**answers

184 views

### Constructing hard inputs for the complement of bounded halting

If there is always a hard input for the complement of bounded halting, can that input be constructed?
More precisely, suppose that
for any deterministic TM $M$ accepting
$$
...

**17**

votes

**5**answers

2k views

### Why relativization can't solve NP !=P?

If this problem is really stupid, please close it. But I really wanna get some answer for it. And I learnt computational complexity by reading books only.
When I learnt to the topic of relativization ...

**1**

vote

**0**answers

1k views

### Quantum computation implications of (P vs NP) [duplicate]

Possible Duplicate:
What impact would P!=NP have on the characterization of BQP?
Before I begin, I had a similar post closed for mentioning the recently released (to be verified) proof that ...

**11**

votes

**2**answers

2k views

### What impact would P!=NP have on the characterization of BQP?

Many complexity theorists assume that $P\ne NP.$ If this is proved, how would it impact quantum computing and quantum algorithms? Would the proof immediately disallow quantum algorithms from ever ...

**23**

votes

**2**answers

1k views

### Given a polynomial-time algorithm, can we compute an explicit polynomial time bound just from the program?

Question. Given a Turing-machine program $e$, which
is guaranteed to run in polynomial time, can we computably
find such a polynomial?
In other words, is there a
computable function $e\mapsto p_e$, ...

**8**

votes

**3**answers

1k views

### Non-existence of algorithm converting NP algorithm to P algorithm?

[Edit: in the light of Nate Eldredge's answer below I rephrase the question]
P=NP is equivalent to the existence of a map of the following form:
Input: a polynomial-time non-deterministic Turing ...

**2**

votes

**1**answer

312 views

### poly-time algorithm to choose elements of sets

Let $A_1,A_2,\ldots,A_k$ be finite sets. Furthermore, for each $i\in\{1,2,\ldots,k\}$, let $B_i$ be a set whose elements are subsets of $A_i$.
Is there any polynomial-time algorithm that decides ...

**5**

votes

**1**answer

496 views

### Minimal Backtracking Proof Tree

When trying to prove that a particular instance of a problem like graph coloring or SAT is unsatisfiable, generally one explores the search tree using an algorithm like DPLL and the proof of ...

**6**

votes

**3**answers

2k views

### Is this a well known NP-complete problem?

I came across this problem recently and I wanted to know whether it was a well known NP-complete problem. I checked the library but could not find anything that matched exactly.
Given a directed ...

**4**

votes

**1**answer

802 views

### BPP being equal to #P under Oracle

Luca Trevisan here gives a randomized polynomial-time approximation algorithm for #3-coloring given an NP oracle.
In a similar vein, I was wondering if there were any results on ...

**18**

votes

**3**answers

3k views

### Satisfiability of general Boolean formulas with at most two occurrences per variable

(If you know basics in theoretical computer science, you may skip immediately to the dark box below. I thought I would try to explain my question very carefully, to maximize the number of people that ...