**7**

votes

**2**answers

118 views

### Isomorphism problem on the class of induced subgraphs of a hypercube

A problem that I am currently studying translates to the problem of deciding whether two induced subgraphs of the hypercube $Q_k$ are isomorphic.
Now it feels to me that this class of graphs is "too ...

**4**

votes

**0**answers

129 views

### Is there a program for theory of incompleteness in NP?

Motivated by Suresh's post, Techniques for showing that problem is in hardness limbo, it seems that there might be an underlying theory that explains why some of these problems can not be complete for ...

**-1**

votes

**0**answers

213 views

### Comparing the Kolmogorov complexity of theories - Part 2

Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(x) > L$ where $K(x)$ is the Kolmogorov complexity of natural number $x$ and $L$ is a sufficiently ...

**4**

votes

**0**answers

163 views

### What is the complexity of intersecting two matrix algebras over a finite field?

The following question arose in a joint project with Arkadius Kalka and Adi Ben-Zvi.
Let $\mathbb{F}$ be a finite field, and $M_n(\mathbb{F})$ be the $n\times n$ matrices over $\mathbb{F}$.
For a ...

**2**

votes

**1**answer

163 views

### NP Hardness proof for permanent of 0-1 matrix [closed]

I am relatively new to complexity and computability theory. I just came across the concept of Permanent of a matrix and read that it is NP hard problem to compute the permanent of 0-1 matrix.
Of ...

**5**

votes

**0**answers

102 views

### Is Hankelability NP-hard?

This question was previously asked on cstheory but with no answers or substantive comments.
I am trying to write code to detect if a matrix is a permutation of a Hankel matrix. Here is the spec.
...

**2**

votes

**0**answers

165 views

### What is the complexity of determining Ramsey Number?

In the notation of Garey and Johnson [1], two problems related to Ramsey Problem were defined:
$\textbf{ARROWING}$
Instance: (Finite) graphs $F$, $G$ and $H$.
Question: Does $F\rightarrow (G, H)$?
...

**1**

vote

**0**answers

72 views

### Complexity :: Integer Programming :: Non-Poly Example [closed]

When learning about computational complexity I find that when discussing the NP-Complete problems authors always give examples of such problems that can in fact be solved in poly time.
I understand ...

**11**

votes

**1**answer

440 views

### Can Shor's Algorithm be modified to run efficiently on a classical computer?

Shor's algorithm is an algorithm which factors integers in polynomial time on a quantum computer. If one tries to run it on a classical computer, one runs into the problem that the state vector that ...

**3**

votes

**0**answers

100 views

### What is known about the complexity of this covering problem?

Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called critical if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex ...

**1**

vote

**0**answers

51 views

### FPTAS for approximating the permanent of a matrix

My question concerns approximating permanent of an $n$-by-$n$ matrix.
Several approximation algorithms have been proposed in the literature for this purpose, whose time complexity depend on $n$ and ...

**1**

vote

**2**answers

174 views

### Algorithm for fast factorization of polynomial over $\mathbb Z$ or over $\mathbb F_p$

I want to fast decompose polynomial over ring of integers (original polynomial has integer coefficients and all of factors have integer coefficients) and also over ring of integers modulo prime ...

**1**

vote

**0**answers

56 views

### What's the complexity of the one sink directed subgraph isomorphism problem?

I am considering trying a new approach for the subgraph isomorphism problem in my PhD, but it just seems to work well for digraphs of one sink. By working well I mean some promise of not having to ...

**1**

vote

**1**answer

173 views

### About expectation norms on graphs

Let $S \subseteq V$ of a $d-$regular graph $G$ such that $\mu = \frac{\vert S \vert }{\vert V \vert } $. Let $A$ be the adjacency matrix of the graph. Then define the quantity $\phi(S)= ...

**0**

votes

**0**answers

85 views

### What is wrong with the argument that zero permanent is polynomial?

This Lecture summarizes some well known facts about $\#P$ completeness of permanent.
Given a CNF formula $\phi$ on $n$ variables, they construct
matrix $A$ such that:
$$perm(A)=4^{3m} \#SAT(\phi)$$
...

**3**

votes

**1**answer

89 views

### What is the Complexity Class of the “Function Variant” of the Integer Factorization Problem?

I've been reading up a lot Prime Factorization and it's complexity, including a fair number of questions on this very site. However, I still feel there is a question still left unanswered.
So, ...

**2**

votes

**1**answer

58 views

### Polynomial degree comparison of Nullstellensatz and Positivstellensatz over real algebraic sets

Suppose we have a (finite) system of polynomials $P = \{ p_i \} \subseteq \mathbb{R}[x_1, \ldots, x_n]$. Then it is well known by the Nullstellensatz that either $P$ has a simultaneous zero over ...

**1**

vote

**1**answer

69 views

### Connection between Barnette conjecture and hardness of cubic graph decomposition

Motivated by this post on cubic graphs decompositions and the connection to Barnette conjecture, I am interested in decomposing a connected bridgeless cubic graph into edge-disjoint paths of length 3 ...

**0**

votes

**1**answer

91 views

### A particular argument in the review on expanders by Hoory-Linial-Wigderson

I am thinking about the third bullet point on page 455 here, http://www.ams.org/journals/bull/2006-43-04/S0273-0979-06-01126-8/
Can someone explain what is the argument there which seems to conclude ...

**5**

votes

**1**answer

314 views

### When are (Abelian) Cayley graphs also expanders?

I want to ask the question in two parts,
(1)
Is there some fundamental distinguishing property between Abelian and non-Abelian Cayley graphs? (say some specific proof technique which distinguishes ...

**2**

votes

**0**answers

104 views

### About the small set expansion conjecture

Given a graph $G=(V,E)$ and a $\delta > 0$ one wants to calculate $h(G,\delta)=min_{\vert S\vert \leq \delta \vert V \vert } \phi(S)$. ($\phi(S) = \frac{ E(S,\bar{S}) }{d min \{\vert S \vert , n - ...

**6**

votes

**0**answers

84 views

### Is there a ``Ladner's Theorem" for the PH-vs-PSPACE scenario?

Like a statement of the kind, ``If the Polynomial Hierarchy (PH) $\neq$ PSPACE then there exists $L \in PSPACE \backslash PH$ which is not PSPACE-complete"?
Or is there something else that states ...

**12**

votes

**1**answer

335 views

### Is factorial definable using a $\Delta_0$ formula?

The factorial function is primitive recursive, and therefore definable by a $\Sigma_1$ formula.
Is it also definable by a $\Delta_0$ formula (i.e. bounded quantifiers)?
If not, why?

**2**

votes

**1**answer

210 views

### Why a tensor product of $2\times 2$ unitaries cannot implement a $3\times 3$ unitary?

Let $\{v_1, \dotsc, v_m\} \in \mathbb{C}^{2^n}$ be a set of orthonormal vectors. Define a map $R_m$ from $2^n \times 2^n$ to $m \times m$ matrices as follows:
$$R_m(M) := \sum_{i,j=1}^m (v_i^*M v_j) ...

**7**

votes

**0**answers

121 views

### Ricocheting pinball-like shot: Complexity?

Suppose one has $n$ perfect two-sided mirror segments in the plane $\mathbb{R}^2$.
The segments are open, excluding their endpoints.
They are disjoint as closed segments, i.e., no pair shares an ...

**4**

votes

**1**answer

195 views

### Explicit bounds for transfer results in algebraic geometry

Assume you have an ideal $I\subseteq\mathbb{Z}[X_1,\ldots,X_n]$ of the polynomial ring in $n$ variables over the integers. For any field $\Bbbk$, I can consider the ideal ...

**3**

votes

**0**answers

62 views

### Are all $k$th-longest-tour problems equally hard?

It is well known, that determining the shortest and, the longest Hamilton Cycle of a complete graph with real edge weights are algorithmically two sides of the same medal: one transforms to the other ...

**0**

votes

**0**answers

65 views

### Confusion about reduction counting vertex covers to counting cycle covers

Cross-posted from cstheory
This confuses me.
One easy case of counting is when the
decision problem is in $P$ and there are no solutions.
A lecture show that the problem of counting the number of ...

**6**

votes

**2**answers

195 views

### Geometric dominating set: NP-complete?

Let $G=(V,E)$ be a geometric graph, a graph embedded in the plane whose edge lengths are
the Euclidean distance between its endpoint vertices.
Say that a set of vertices $D \subseteq V$ is a geometric ...

**11**

votes

**0**answers

717 views

### Primes and Parity

This problem is motivated by the polymath4 project. There, the aim was to find an efficient deterministic algorithm for finding a prime larger than $N$. The hope was to find a polynomial algorithm in ...

**4**

votes

**1**answer

161 views

### Tiling with restricted overlap

Non-overlapping tilings of regions is a well-studied topic.
I wonder if the following variant has been considered:
A tile can be partitioned into several regions, where such regions from different ...

**7**

votes

**2**answers

222 views

### Recent trends in effective analysis

The references listed at http://en.wikipedia.org/wiki/Computable_analysis have all been published 30-15 years ago. Are the approaches which these references expose still up-to-date and relevant to the ...

**11**

votes

**5**answers

1k views

### Bounds for constructing $n!$ with additions, subtractions, and multiplications starting from $1$

Found this on Complexity Zoo warning expired certificate
check NP Over The Complex Numbers.
[BCS+97] show the following striking result. For a positive integer $n$, let $t(n)$ denote the minimum ...

**1**

vote

**1**answer

107 views

### Graph classes where finding explicit coloring have certificate that it is minumum

Graph coloring doesn't have certificate that smaller coloring doesn't exist in general.
I am looking for graph classes where finding explicit coloring is not polynomial and have polynomially ...

**2**

votes

**1**answer

140 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

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

**1**

vote

**0**answers

111 views

### Determining strong base-orderability of a matroid

A matroid is said to be strongly base-orderable when for any two bases $B_1,B_2$ there exists a bijection $f:B_1 \mapsto B_2$ such that for any $X\subseteq B_1$ set $B_1 - X+ f(X)$ is also a base.
...

**2**

votes

**0**answers

110 views

### Number of degree $k$ functions [closed]

Given a Boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$, there is a real multivariate multilinear polynomial that is associated with in through interpolation.
Example: ...

**4**

votes

**2**answers

197 views

### Complexity of finding the maximum sum divided by product

What is the complexity of the following optimization problem?
Problem.
Given $n$ pairs of positive reals $(a_i,b_i)_{i=1}^n$, choose a subset $S \subseteq [n]$ to maximize
$$
\frac{\sum_{i\in S} ...

**2**

votes

**1**answer

58 views

### What is Known about Preprocessing for Stabbing Queries?

In a concrete setting, I have the following problem:
given a fixed set of simple objects (e.g. disks or, convex polygons with few vertices), I need to quickly report the objects that are hit (i.e. ...

**7**

votes

**0**answers

141 views

### Is there an infinite increasing sequence of naturals for which Landau's function can be efficiently computed?

Landau's function
$g(n)$ is the largest order of an element of the symmetric group $S_n$.
Equivalently, $g(n)$ is the largest least common multiple (lcm) of any partition of $n$.
In general $g(n)$ is ...

**2**

votes

**1**answer

356 views

### Given a set of 2D vertices, how to create a minimum-area polygon which contains all the given vertices?

Not sure whether this question belongs here or math.stackexchange.
You can assume that all the vertices are unique. The given vertices can be the vertices of the polygon, thus they do NOT have to be ...

**7**

votes

**0**answers

332 views

### Evidence that Graph Isomorphism problem is not $NP$-complete

Graph isomorphism problem is one of the longest standing problems that resisted classification into $P$ or $NP$-complete problems. We have evidences that it can not be $NP$-complete. Firstly, Graph ...

**3**

votes

**0**answers

110 views

### On the computational complexity of the Hilbert polynomial of numerical semigroup rings

Let $(R, \mathfrak{m}) = k[[X^a, X^b, X^c]]$, $a<b<c$, $gcd(a, b, c) = 1$, be a semigroup ring. We have $R$ is a Cohen-Macaulay local ring of dimension one. It is well known that ...

**3**

votes

**1**answer

132 views

### Sorting interleaved sorted lists

By interleaving two lists I mean to combine them into a single list in any way that maintains the relative order of the elements coming from each list. For example, interleaving $(x_1,x_2,x_3)$ and ...

**5**

votes

**1**answer

165 views

### Finding sparsest solution of a linear system

I want to find the solution with most zero-components for the following problem:
$Ax=b$ for $A\in \mathbb{R}^{k\times n}, b \in \mathbb{R}^{k},k<n$, where $x$ is real and has no additional ...

**2**

votes

**0**answers

56 views

### Recognizing sequences sortable by transpositions?

While reading the post, Probability of generating a desired permutation by random swaps, by Aaronson, and to continue my program I started in this post, How hard is reconstructing a permutation from ...

**1**

vote

**0**answers

62 views

### Reducing enumeration of reduced words in general Coxeter groups to another #P-complete problem

There is a polynomial time algorithm that takes as inputs a Coxeter system $(W,S)$ with $S$ finite (but with $W$ not necessarily finite), say encoded as a Coxeter matrix, as well as two reduced words ...

**-2**

votes

**2**answers

177 views

### Time estimate to determine if a number is prime [closed]

How long does it take to verify that a given number is a prime number, as a function of its number of digits, in a personal computer, say? How computationally hard is this?

**12**

votes

**1**answer

545 views

### Is there a known primitive recursive upper bound on the nth “Zhang prime”

(This question is pure curiosity. Feel free to close it if you feel it is not appropriate for mathoverflow.)
In 2013 Zhang showed that there are infinitely many pairs of primes which are less that ...