computational complexity theory; complexity classes, such as P, NP, PSPACE, and so on; resource-limited computation; NP-completeness and other completeness concepts; oracle analogues of complexity classes; complexity-theoretic computational models such as automata, circuits; regular languages; ...

learn more… | top users | synonyms (1)

1
vote
1answer
89 views

$0/1$ programming multiple quadratic constraints

If we have an $n$-variable rank $n$-linear system it is clear we can find whether there exists a $0/1$ solution in polynomial time. If we have an $n$-variable degree $2$ system how many constraints ...
3
votes
0answers
22 views

Complexity of OBDD isomorphism (representing same function after permutation of variables)?

According to wikipedia Ordered Binary Decision Diagarams (OBDD) are a data structure that is used to represent a Boolean function. OBDD is a DAG with two sinks $0,1$. The size of the BDD is number ...
2
votes
1answer
246 views

Can we solve Hamiltonian Path problem for biconnected planar graphs in linear time?

Assume that we have a bi-connected planar graph $G$ with $\Delta(G)>3$, and we want to find a Hamiltonian Path in $G$. As we know the st-order of a bi-connected planar graph can be computed in ...
2
votes
0answers
170 views

Derandomization barriers in complexity theory applicable as barriers to constructive arguments replacing probabilistic method

The probabilistic method as first pioneered by Erdős (although others used this before) shows existence of a certain object while finding that object may take exponential time. (1) Is there any ...
3
votes
1answer
572 views

Claimed Quadrature Results seem Impossible

We've been preparing a preprint that shows that the convergence bounds proved for tanh-sinh quadrature for numerical integration, cannot possibly hold, and an error must exist - since they imply a P ...
5
votes
1answer
285 views

Division by $n$ in elliptic curves

Let $E/\mathbb F_{p^m}$ be an arbitrary elliptic curve over the Galois field $\mathbb F_{p^m}$, and let $$[n]^{-1}(P)\cap E(\mathbb F_{p^m})=\{Q\in E(\mathbb F_{p^m})\mid nQ=P\}.$$ Also let $N=\#E(\...
11
votes
3answers
412 views

Algorithmic complexity of formal proof verification?

In this question, suppose $S$ is some popular real-world automated proof system that is stronger than or equivalent to Peano Arithmetic. I would be happy with a positive answer to the following for ...
2
votes
1answer
53 views

Complexity of recognizing equivalent translation surfaces

"A translation surface is a union of polygons with pairs of parallel edges identified by translation, up to cut and paste equivalence." I take that succinct (and not fully precise) definition from a ...
4
votes
1answer
85 views

Complexity of this minimization

For integer $N$ consider the mapping $$f : (0,1)^N \to \mathbb{R}, \quad x \mapsto \min_{b \in \{0,1\}^N} \left\{ x^b + x^{1-b} \right\},$$ where $x^b = x_1^{b_1} \cdots x_N^{b_N}$ and $1-b = (1-b_1, \...
5
votes
1answer
407 views

Complexity of linear solvers vs matrix inversion

Solving linear equations can be reduced to a matrix-inversion problem, implying that the time complexity of the former problem is not greater than the time complexity of the latter. Conversely, given ...
1
vote
1answer
183 views

On Knot Equivalence problem statement

How is the knot equivalence problem represented? By this I mean I am looking for an analogy that compares with graph equivalence. For graph equivalence, we have two graphs $G_1$ and $G_2$ with ...
16
votes
1answer
1k views

Is it possible to make an algorithm that could predict the likelihood that a program will halt?

Today I began to read about computability theory. I do not even have an elementary understanding of the topic but it certainly got me thinking. I know there is there is no 'one-for-all' algorithm that ...
1
vote
1answer
154 views

Complexity of $\mathsf{gcd}(a,b)\bmod N$

Given $a,b\in\Bbb N$ where each $a,b$ is $n$-bits, we can compute $\mathsf{gcd}(a,b)$ in $cn^{1+\epsilon}$ bit operations for some fixed $c\geq1$. My query is given $N,a,b$ where $a,b$ is $n$-bits ...
1
vote
0answers
53 views

Complexity theory and closed form formulas in analysis

My question concerns definitions of "closed form" solutions. In hamiltonian systems this is closely related to complete integrability. In this context closed form can refers to having $(q(t),p(t))$ ...
2
votes
2answers
272 views

Time Hierarchy Theorem and P vs NP

One obvious strategy for proving P not equal to NP would be to show that there is some problem in NP which is hard for a time class strictly containing P (the origin of this question is the recent ...
53
votes
3answers
4k views

What are the implications of the new quasi-polynomial time solution for the Graph Isomorphism problem?

This week, news came out that Laszlo Babai has found a quasi-polynomial time algorithm to solve the Graph Isomorphism problem (that is: $O(\exp(polylog(n)))$). He is giving a series of talks this week,...
2
votes
1answer
226 views

Effectively non-recursiveness of some sets

A set $A$ is completely productive if there exists a computable function $f$ such that for every $e$, $f(e)\in (A-W_e)\cup (W_e-A)$‎. ‎A set is effectively non-recursive if it is r.e‎. ‎and its ...
1
vote
1answer
161 views

What is the fastest way to sort numbers lexicographically?

I have $N$ sequences of numbers. None of them is longer than $10^6$. I want to sort those sequences lexicographically. For example, given sequences {1, 2, 4}, {1, 2, 3}, {2, 5, 7}, {2}, I want to have ...
1
vote
0answers
76 views

On variant of integer factorization

In the post on site cstheory.stackexchange on whether a variant of integer factorization $$\mathsf{}\mbox{ }{\Pi} = \{\langle a, b, n \rangle \;|\; \exists \mbox{ } \mathsf{ an}\mbox{ }\mathsf{ ...
1
vote
0answers
84 views

A reference for “Borel Sets and Circuit Complexity”

Is there any pdf version of M.Sipser's "Borel Sets and Circuit Complexity" or , since I am unable to get this paper, is there other reference closely related to theory in that paper?
1
vote
0answers
22 views

Complexity of finding algebraic dependency of polynomials over the rationals or in a finite field?

Let $f_1,\ldots f_m \in K[x_1,\ldots,x_n]$ where $K$ is $\mathbb{Q}$ or a finite field. Q1 What is the complexity of finding all algebraic dependencies between $f_i$? Q2 What is the ...
3
votes
1answer
145 views

Computational complexity of low rank SDP

Suppose we are given a general SDP of the form with an additinal rank requirement \begin{array}{rl} {\displaystyle\min_{X \in \mathbb{S}^n}} & \langle C, X \rangle_{\mathbb{S}^n} \\ \text{subject ...
4
votes
0answers
407 views

Weighted Median Filtering

Let's begin with a little review of unweighted median filtering. Suppose I have a list of $N$ real-valued numbers, $x=x_1,...,x_N$. Let $m_i$ be the median of $K$ consecutive values: $m_i=$ median$(...
14
votes
0answers
142 views

Complexity classes for BSS machines

Given a first-order structure $\mathcal{S}$, a Blum-Shub-Smale machine on $\mathcal{S}$ is essentially a Turing machine where Cells on the tape can hold arbitrary elements of $\mathcal{S}$. The ...
3
votes
1answer
135 views

Equivalence between Diffie Hellman and Discrete Log

For which non-trivial groups, do we know that the Diffie Hellman problem and the Discrete Log are equivalent? Is there any group for which we suspect them to be different? Could there be a finite ...
2
votes
0answers
203 views

Avoiding Chinese Remainder Theorem

Given $k\in\Bbb N$ with $k<(\log_2N)^{\frac1\alpha}$ where $\alpha>2$ is fixed and $N$ being some integer such that $$N<\prod_{i=1}^k\pi_i^{a_i}$$ where $\pi_1,\pi_2,\dots,\pi_{k-1},\pi_k$ ...
1
vote
2answers
66 views

Maximum subgraph edge distance greater than given number

I have a weighted graph G with approximately 75000 nodes. I would like to find subgraph G' induced on a subset of nodes, such that all edge weights in G' are greater than a given constant C and the ...
5
votes
0answers
143 views

Is there a decomposition strengthening of the Sauer-Shelah Lemma?

Let $S \subset \{-1,1\}^n$. For a subset $A \subset [n]$ let $P_A$ denote the coordinate projection operator on S; in other words let $P_A(S)$ be the coordinate projection of $S$ onto the coordinates ...
5
votes
2answers
238 views

How can I prove that these two graph coloring problems are polynomial time equivalent?

Given a graph $G(V,E)$. The standard $k$-coloring problem consists in finding a feasible coloring (no two adjacent nodes share the same color) of the nodes with $k$ colors. Let this problem be $P_1$. ...
3
votes
1answer
121 views

Construction of planar embedding

I'm reading the following paper on universality considerations in VLSI circuits http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf In Theorem 2 On the second page it states there exists ...
2
votes
0answers
126 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 ...
2
votes
0answers
92 views

Worst case performance of a simple averaging algorithm

Let $u_1,\ldots,u_n$ be a sequence of rationals with finite binary expansion. Consider the following simple averaging algorithm: while the sequence is not monotone increasing, pick $i$ with $u_{i+1}&...
6
votes
1answer
173 views

Shortest vector problem over polynomials

In shortest vector problem, given a lattice in $\Bbb Z^n$, we seek the shortest non-zero vector in the lattice. This problem is computationally difficult. Is there a polynomial analog of this problem ...
3
votes
0answers
62 views

Existence of universal witness set and efficient sampling of coNP sets

Inspired by this answer given by Noam, which (I think) implies that a set $A \in NP$ if and only if there is polynomial-time computable function $f$ from random strings to elements of $A$ such that $A$...
3
votes
1answer
131 views

Complexity of a very simple graph partitioning problem

The following problem seems like a very simple and natural one, but I am not familiar with any existing work on it; in particular I am hoping to prove it is NP hard: Let $G$ be a complete weighted ...
4
votes
1answer
100 views

testing singularity of integer matrices

I am looking for the best upper bounds on the bit complexity for testing the singularity of an integer $n\times n$ matrix, where each integer is represented with $k$ bits. I know the fast method for ...
7
votes
1answer
173 views

“Separated” version of Sauer's lemma on VC classes

Sauer's lemma, a well-known result in computational complexity theory, learning theory, and combinatorics, states the following: Let $\Phi$ be a collection of subsets of a set $U$, and assume that ...
3
votes
0answers
230 views

A factorial related statement

Is the following promise problem in $\mathsf{NP}$ or $\mathsf{coNP}$ or even in $\mathsf{PH}$? $$\Pi:\mathsf{Given}\mbox{ }p,a,s\in\Bbb N,\mbox{ }\mathsf{with}\mbox{ }p\mbox{ }\mathsf{a}\mbox{ }\...
0
votes
0answers
277 views

Probability two random intervals overlap

I'm working on an algorithm for orthogonal line intersection detection and am trying to analyze some things about it. For simplicity, we can consider the problem as follows: Given N randomly ...
3
votes
1answer
106 views

Understanding Corollary 3, Sec. 5.6, of Papadimitriou's Computational Complexity

I am struggling to understand Corollary 3 from Section 5.6 of Papadimitriou's Complexity Theory book (Addison-Wesley, 1993). It got me completely confused... If anyone out there has read it and ...
8
votes
1answer
188 views

Most computationally efficient Littlewood-Richardson rule

There are many, many different versions of the Littlewood-Richardson rule: the original characterization via Yamanouchi words, Remmel's version, a description via the Poirier-Reutenauer bialgebra, the ...
0
votes
0answers
69 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. ...
18
votes
0answers
561 views

Reference request: Parallel processor theorem of William Thurston

Sometime in the 1980's or 1990's, Bill Thurston proved a theorem regarding the existence of a universal parallel processing machine, using a certain class for such machines having finite deterministic ...
3
votes
0answers
108 views

Oracle queries asked in parallel

Definition: Assume that $\phi(q)$ is of the form $\exists y \leq 2^{p(n)} \varphi(q,y)$, where $p$ is a polynomial and $n = |q|$ (i.e. $n$ is the length of the binary representation of $q$). Then a ...
3
votes
0answers
245 views

Possible $\mathsf{NP}$ complete problem from number theory

A candidate $\mathsf{NP}$ complete variant of factoring was posted in http://cstheory.stackexchange.com/questions/4769/an-np-complete-variant-of-factoring, where decision problem $\text{BOUNDED-...
3
votes
0answers
53 views

$n!$ computation in $\mathsf{BSS}$ model

It is well known that if $n!$ cannot be computed in $\mathsf{polylog}(n)$ ring ($\Bbb Z$) operations, then $\mathsf P\neq\mathsf{NP}$ in $\mathsf{BSS}$ model. Suppose if we assume $\mathsf P=\mathsf{...
1
vote
0answers
32 views

Relation between indexed languages (OI-macro or context-free tree) and scattered context languages

I'm not sure about the relation between indexed languages (generated by indexed grammars--Aho) and scattered context languages (generated by scattered context grammars--J Hopcroft). I think that ...
2
votes
1answer
199 views

Complexity of sparse matrix-vector multiplication?

I have a vector $\mathbf{x}$ of size $m\cdot n$ of zeros and ones, i.e., $\mathbf{x}\in\{0,1\}^{m\cdot n}$ and a matrix $\mathbf{A}$ of size $\left(m\cdot n+m+n+1\right)\times\left(m\cdot n\right)$ of ...
1
vote
0answers
39 views

Canonical representation of binary decision trees in Ptime?

I am wondering about the possibility of efficiently (here: in Ptime) representing binary decision trees (BDT) by some other data structure in a way that characterizes their equivalence. More ...
0
votes
0answers
27 views

Complexity of edge coloring graphs of sufficiently large maximum degree

I am interested in the complexity of edge coloring graphs with $\Delta(G) > |V(G)|/3$. This is closely related to the Overfull conjecture (OC). Conjecture/Question: If a simple graph G with n ...