The np tag has no usage guidance.

**2**

votes

**0**answers

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

**0**

votes

**0**answers

58 views

### Efficient recognition of sequences sortable by transpositions?

While reading the post, Probability of generating a desired permutation by random swaps, by Aaronson, I got interested in this sorting problem:
Input: a sequence $A$ of $2N$ positive integers.
...

**2**

votes

**1**answer

147 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

70 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

213 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

111 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

**2**answers

517 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

689 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

105 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

149 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

362 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

401 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

599 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

172 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

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

**29**

votes

**1**answer

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

151 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

234 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

226 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

99 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

277 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

131 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

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

**13**

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

97 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

226 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

274 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

658 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

559 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

953 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

797 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

251 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

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

**1**

vote

**1**answer

718 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

538 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

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

**8**

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

944 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

625 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

571 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

252 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

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

**4**

votes

**1**answer

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

**20**

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

2k 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

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