**22**

votes

**0**answers

539 views

### A combination of two well-known complexity problems

Suppose you are given two graphs $G$ and $H$ and are told that one of the following two situations occurs. Either they are isomorphic, or one of the graphs contains a Hamilton cycle and the other ...

**17**

votes

**0**answers

428 views

### Computational complexity of topological K-theory

I am a novice with K-theory trying to understand what is and what is not possible.
Given a finite simplicial complex $X$, there of course elementary ways to quickly compute the cohomology of $X$ with ...

**12**

votes

**0**answers

2k views

### How can an approach to $P$ vs $NP$ based on descriptive complexity avoid being a natural proof in the sense of Raborov-Rudich?

EDIT: This question has been modified to make it a stand-alone question. Feel free to retract your votes for the previous version.
Here are Vinay Deolalikar's paper, and Richard Lipton's first post ...

**12**

votes

**0**answers

1k views

### Razborov's response to Almost Natural Proofs

This post is about Natural Proofs barrier in computational complexity.
There are two recent papers related to this. They are:
Amplifying lower bounds by means of self-reducibility by Eric Allender ...

**11**

votes

**0**answers

307 views

### Splay trees and Thompson's group $F$

( I apologize for only indicating some easy to find references, but new users are not allowed to link more than five). This is very speculative, but:
Question: Is there a reformulation of the Dynamic ...

**11**

votes

**0**answers

565 views

### Regular languages of matrices and their generating functions

My question is somewhat related to this question.
Let us fix natural numbers $k$ and $C$. Let $A$ be an automaton whose alphabet consists of $k\times k$ matrices with integer coefficients of ...

**9**

votes

**0**answers

1k views

### Is Witten's new method of quantization useful for geometric complexity theory?

The Kempf-Ness theorem (see e.g. arXiv:0912.1132) - that the algebraic quotient of geometric invariant theory is also a symplectic quotient - suggests (to me) that certain physical constructions used ...

**8**

votes

**0**answers

193 views

### Computing van Kampen diagrams

If G is a finitely presented group (with generating set X) and w is a word over X such that
w=1 in G, then the latter can be witnessed by a so called van Kampen diagram for w, which is
a planar ...

**8**

votes

**0**answers

459 views

### Is the dominating set problem restricted to planar bipartite graphs of maximum degree 3 NP-complete?

Does anyone know about an NP-completeness result for the DOMINATING SET problem in graphs, restricted to the class of planar bipartite graphs of maximum degree 3?
I know it is NP-complete for the ...

**8**

votes

**0**answers

945 views

### Weighted Hamming distance

Basically my question is, what kind of geometry do we get if we use a "weighted" Hamming distance. This is combinatorics but similar things come up sometimes in theoretical computer science, for ...

**6**

votes

**0**answers

316 views

### Any reason to believe that $NP \neq P$ is unprovable in ZFC

We know $NP \neq P$ from a lot of point of view like empirical reason,or theoretical reasons such as finite model theory or descriptive complexity.Although we find so many reasons to believe $NP \neq ...

**6**

votes

**0**answers

169 views

### When is a reduction not a reduction?

Every mathematician understands the concept of reducing a complicated problem to a simpler problem. "Without loss of generality, we may assume…" However, I've noticed that some kinds of ...

**6**

votes

**0**answers

117 views

### An explicit IP algorithm for chess?

If I have 2 large graphs to be tested for isomorphism, and can communicate with some (powerfull but untrusted) machine, I can choose graph at random, permute vertices, ask machine to guess which one ...

**6**

votes

**0**answers

245 views

### Is integer GCD in NC?

Wikipedia, in the page http://en.wikipedia.org/wiki/Greatest_common_divisor#Complexity mentions integer GCD is in NC by citing http://www.cs.cornell.edu/courses/CS6820/2012sp/Handouts/Sedjelmaci07.pdf
...

**6**

votes

**0**answers

276 views

### Enumerating (generalized) de Bruijn tori

Given a cyclic word $w$ of length $N$ over a $q$-ary alphabet and $k \in \mathbb{Z}_+$, consider the directed multigraph $G_k(w) = (V,E)$ with $V \subset$ {$1,\dots,q$}$^k$ given by the $k$-lets ...

**5**

votes

**0**answers

183 views

### Is simultaneous diophantine approximation (in a weaker sense) NP hard?

The traditional problem of simultaneous diophantine approximation is: Given a set of rational numbers $g_1,\ldots,g_d$, an integer $N$, and a rational $\gamma>0$, is there an integer $W$ with ...

**5**

votes

**0**answers

113 views

### Complexity of finding three perfect matchings with no edge in common in a bridgeless cubic graph

According to a conjecture:
Conjecture (Fan & Raspaud, 1994) Every bridgeless cubic graph contains three perfect matchings with no edge in common.
Equivalent statement here
Main question:
...

**5**

votes

**0**answers

85 views

### Can the isomorphism relation for countable models become harder when adding finitely many constants?

I am particularly interesting in the case where $T$ is o-minimal, but I would be interested in any theory $T$ (or even an $L_{\omega_1,\omega}$-sentence) which has this property.
Context: view the ...

**5**

votes

**0**answers

158 views

### Feasible Type Theories

I am looking for references about efficient type theories,
efficiency in the sense of computational complexity,
and type theory in the sense of Martin-Lof's type theories.
Has there been any studies ...

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

**4**

votes

**0**answers

239 views

### About “natural proof” of Razborov and Rudich

The famous "Natural Proof" paper ,http://www.cs.umd.edu/~gasarch/BLOGPAPERS/natural.pdf , of Razborov and Rudich gives a barrier for any proof that try to separate P and NP. It mainly shows that if ...

**4**

votes

**0**answers

151 views

### Nesting big-O with big-Omega $O(g(\Omega(h(n))))$: is it $O$ for all $\Omega$ or for one $\Omega$?

I want to express the following statement about a function $f(n)$: there exists $f_\Omega\in\Omega(h(n))$ such that $f\in O(g(f_\Omega(n))$. What's the correct notation for this? Is it $f\in ...

**4**

votes

**0**answers

385 views

### Computational complexity of multiplication in a nilpotent group?

What is the computational complexity of multiplication in a Carnot group ?
Background: A Carnot group is a real nilpotent Lie group $N$ whose Lie algebra $Lie(N)$ admits a direct sum decomposition
...

**4**

votes

**0**answers

164 views

### Suppose P = BPP; Pseudorandom Generators vs NP Adversary

Suppose P = BPP.
Then we know there exist pseudorandom number generators vs P.
Suppose the adversary is NP.
Now, any pseudorandom number generator that only uses P will fail. (Since NP can invert ...

**4**

votes

**0**answers

211 views

### Domination in Nice Lattices

Let an integer vector be nice when it has only two nonzero components, which sum to zero. So (0, 0, 3, 0, -3) and (-1, 0, 1, 0, 0) are examples of nice vectors in $n=5$ dimensions.
Call a lattice ...

**4**

votes

**0**answers

298 views

### Can the Littlewood-Richardson cone be used for combinatorial optimization?

The Littlewood-Richardson cone $LR_{n, k}$ consists of all $k-$tuples $(a_1, a_2, \dots, a_k)$ of real $n-$vectors with monotonically decreasing entries such that there exist $k$ $n \times ...

**3**

votes

**0**answers

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

**3**

votes

**0**answers

113 views

### Gaussian Elimination in terms of Group Action

Gaussian elimination makes determinant of a matrix polynomial-time computable. The reduction of complexity in computing the determinant, which is otherwise sum of exponential terms, is due to presence ...

**3**

votes

**0**answers

173 views

### Kolmogorov complexity with bounded ressources

Thanks to symetry of information (i.e $\forall x,y, K(xy) = K(x) + K(y|x) - O(log(|x| + |y|)$), one can easily show that :
$ \exists N \forall x, (|x| = n^{log(n)} and |x| \geq N), \exists y, (|y| ...

**3**

votes

**0**answers

154 views

### Best lower bound for proof complexity of graph asymmetry

Graph automorphism problem ( GA) of determining whether a graph has a nontrivial automorphism is a good candidate for a problem in $NP$-intermediate. I'm looking for references that study the ...

**3**

votes

**0**answers

310 views

### Connected Sum Decomposition of a Knot

Given a composite knot, is it possible to decompose it in prime knots by an algorithm that runs in polynomial time?

**3**

votes

**0**answers

279 views

### Amortized analysis of data structure via potential function

One common method for proving that a data structure supports an operation in $O(f(n))$ amortized time is to construct a potential function $\Phi: \mathcal S \rightarrow \mathbf R^{+}$, which ...

**3**

votes

**0**answers

194 views

### Algorithm for testing satisfiable fraction of linear equations mod 2

Hello
Let $F_{n,p}$ be a random process which generates a system of linear equations over $F_2$. The variables are $\{x_1, ..., x_n\}$ and for each of the $ \binom{n}{2}$ $i,j$ pairs, the equation ...

**3**

votes

**0**answers

320 views

### Complexity of edge coloring in planar graphs?

I asked this on StackExchange TCS but did not get a satisfactory answer:
Four Color Theorem is equivalent to "Every cubic planar bridgeless graphs is 3-edge colorable". However, 3-edge coloring of ...

**3**

votes

**0**answers

599 views

### Why isn't Montgomery modular exponentiation considered for use in quantum factoring?

It is well known that modular exponentiation (the main part of an RSA operation) is computationally expensive, and as far as I understand things the technique of Montgomery modular exponentiation is ...

**3**

votes

**0**answers

200 views

### For Ising models on finite graphs, is the gradient of Z (w/r/t coupling and field) easier to compute than Z?

Suppose we have a graph $G$ with $n$ vertices, edgeset $E$, $\mathcal{X}=\{1,-1\}^n$. The partition function of the spin-1/2 Ising model on $G$ is
$$Z(J,h)=\sum_{x\in \mathcal{X}} \exp\left(J ...

**3**

votes

**0**answers

379 views

### Does $EXP\neq ZPP$ implies sub-exponential simulation of BPP or NP?

By simulation I mean in the Impaglazzio-Widgerson [IW98] sense, i.e sub-exponential deterministic simulation which appears correct i.o to every efficient adversary.
I think this is a proof:
if ...

**3**

votes

**0**answers

275 views

### To what extent MSO = WS1S, when adding relations?

Let me first clarify my definitions. For a word $w \in \Sigma^*$, with $\Sigma=\{a_1, \ldots, a_n\}$, I define two structures:
$${\mathbb{N}}(w) = \langle {\mathbb{N}}, <, Q_{a_1}, \ldots, Q_{a_n} ...

**2**

votes

**0**answers

43 views

### Computing basis of a lower set given basis of complementary upper set

In a poset $P$, $U\subseteq P$ is an upper set when for all $x\in U$, we have $y\ge x$ implies $y\in U$. Any subset of $P$ generates an upper set, and the basis of an upper set $U$ is the smallest ...

**2**

votes

**0**answers

80 views

### Existence of roots of high order polynomial over finite fields

I want to solve the following question:
Consider a polynomial $f(x)=a_0+a_1*x^{e_1}+a_2*x^{e_2}+\cdots+x^{e_m}\in F_p[x]$ where $p$ is a prime such that $\log(p)\sim m$ and $e_m\sim 2^m$, I want to ...

**2**

votes

**0**answers

166 views

### Computing the chromatic polynomial of graph modulo $x-3$

The chromatic polynomial of graph $P(G,x)$ is univariate
polynomial which counts the number of colorings of $G$
with $x$ colors for natural $x$.
Graph is not $k$ colorable iff $P(G,k)=0$.
The ...

**2**

votes

**0**answers

120 views

### characterization of all periodic tiling of a simple set of Wang Tile

Consider a set of Wang Tile such that all the edges are either 1 or 0.... there are 16 elements in such a set.
Now, I wish to characterize all the periodic tilings of this set (better if they are ...

**2**

votes

**0**answers

75 views

### Complexity of counting words of given length in regular or context-free language

Let $L$ be a regular or context-free language over
alphabet $\{0,1\}$.
What is the complexity of counting words of length $n$ in $L$?
Is it possible to efficiently find if for given $n$
all words ...

**2**

votes

**0**answers

112 views

### Reference Request: Properties of the Integer Factorization Polytope

The complexity of Integer Factorization is to my knowledge still an open problem, whereas deciding, whether a given integer is a prime number is known to be in $P$ and a proof is available online ...

**2**

votes

**0**answers

217 views

### cyclotomic polynomials of given degree

Is there a fast algorithm to generate all cyclotomic polynomials $\Phi_n$ for which the degree of $\Phi_n$ is a fixed constant $d?$ This is obviously related to the "inverse totient" function: compute ...

**2**

votes

**0**answers

134 views

### Odds of projections of a point not on the hyperplane

Let $\mathcal{L}=\{\Bbb x\in\Bbb R^n:x_1+x_2+\dots+x_n=0\}$ be a specific hyperplane.
Let a projection of $c\in\Bbb R^n$ be $p(c)=[p_1,p_2,\dots,p_n]$ where $p_i\neq c_i\implies p_i=0$.
Let ...

**2**

votes

**0**answers

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

**2**

votes

**0**answers

55 views

### Is the $d$-dimensional Arrangement of Trees still $NP$-hard?

The $d$-dimensional Arrangement Problem for general graphs is known to be $NP$-hard since the special case $d=1$ (OLA) already is (Garey et al, [1976]). For Trees however, the one dimensional case can ...

**2**

votes

**0**answers

109 views

### supersingular curve detector

Suppose I give you a prime $p$ and ask for a non-CM supersingular elliptic curve over $\mathbb{F}_p.$ Can this be done in polynomial time (so, polynomial in $\log p$)?

**2**

votes

**0**answers

176 views

### A natural problem on “cartesian union” of set families (hypergraphs). Does anybody know NP-complete problems related to the notion of cartesian product?

I'm curious whether the problem below is NP-complete.
I provide two simple definitions and one example at first.
Definition 1.
Let $\langle {\cal{S}}_i\rangle\substack{i\in I}$ and $\langle ...