**22**

votes

**0**answers

529 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

407 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

296 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

183 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

448 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

886 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

166 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

115 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

244 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

269 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

112 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

148 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

106 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

223 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

122 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

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

**4**

votes

**0**answers

359 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

160 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

209 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

295 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

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

**3**

votes

**0**answers

145 views

### If a graph invariant is NP-Hard, is its “deck ratio” NP-Hard as well?

This question is inspired by the Graph Reconstruction Conjecture. Suppose that $\psi$ is some graph invariant and that it is NP-Hard. There is a plethora of examples, of course. Now define ...

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

171 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

153 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

298 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

270 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

191 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

318 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

588 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

375 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

272 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

142 views

### How hard is a variant of graph automorphism problem?

I'm interested in a variant of graph automorphism problem (which is prime candidate for $NP$-Intermediate problem).
Restricted GA
Input: Given an undirected graph $G(E, V)$, and $\epsilon |V|/2$ ...

**2**

votes

**0**answers

101 views

### Graph theoretical representation of Wang Tile

We note that for one dimensional tiling problem of Wang Tile could be represented by a graph. Each cycle on the graph represents a periodic solution.
However, is there a well established counter-part ...

**2**

votes

**0**answers

68 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

103 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

**0**answers

108 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

132 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

118 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

51 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

107 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

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

**2**

votes

**0**answers

176 views

### Complexity of bipartite graphs and their matchings.

My question concerns a hypothetical family of bipartite graphs, $G_i$.
Each graph $G_i$ has $2^i$ red nodes and $2^i$ blue nodes - so nodes get labelled
by their color and a binary string of ...

**2**

votes

**0**answers

109 views

### Circuits by Level

Context: googling existing results on Circuit Complexity.
I'm aware there are classes like AC, ACC, TC, NC, etc..
Now, suppose I have a circuit, it has the following additional program:
The circuit ...