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
0answers
61 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 ...
2
votes
0answers
195 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 ...
7
votes
0answers
406 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 ...
5
votes
1answer
130 views

Computation Time of Smith Normal Form in Maple

I am using maple to compute the Smith Normal Form of a matrix of size 120*120 and it seems that I will never get an answer back. I have checked my code for small cases and I believe that it is ...
3
votes
0answers
39 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 ...
1
vote
2answers
362 views

When is a power of an indeterminate in an ideal with 2 generators?

If I have an ideal ${\frak a} \colon= (f(X,S), g(X,S))$ of height $2$ in ${\Bbb C}[X, S]$, is it easy to know what power of $S$ is contained in $\frak a$? For example, what is the minimal number $m$? ...
2
votes
1answer
61 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
16 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 ...
-1
votes
0answers
162 views

Straight line complexity of $k!a$ where $(a,p)=1$

In Qi Cheng's paper, an algorithm is provided to calculate $k!a$ at some random $a∈ℕ$ ($a$ is not input to algorithm, only $k$ is), what is the probability that given a prime $p$ such that ...
7
votes
6answers
1k views

Which model of computation is “the best”?

In 1937 Turing described a Turing machine. Since then many models of computation have been decribed in attempt to find a model which is like a real computer but still simple enough to design and ...
0
votes
0answers
21 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 ...
12
votes
1answer
865 views

A generalization of the triangle counting problem for simple weighted graphs

One nice identity is that $$\operatorname{tr}(A^3)/6$$ counts the number of triangles of a graph with adjacency matrix $A$. It also implies that triangle counting in a graph can be performed in ...
9
votes
2answers
1k views

How to determine if there exists a non-zero vector in the kernel

If you are given a $0$-$1$ circulant matrix with $n$ rows and $n$ columns, is there an efficient way of determining if there exists a non-zero $\{-1,0,1\}$-vector in its kernel? Could this problem ...
8
votes
0answers
168 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
0answers
143 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 ...
17
votes
5answers
4k views

The problem of finding the first digit in Graham's number

Motivation In this BBC video about infinity they mention Graham's number. In the second part, Graham mentions that "maybe no one will ever know what [the first] digit is". This made me think: Could ...
0
votes
0answers
16 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 ...
4
votes
0answers
39 views

Digraph weak connectivity in $O(V)$ space and $O(V+E)$ time

A digraph is called weakly connected if its underlying undirected graph is connected. You are given a digraph $G$ with $V$ vertices and $E$ edges as a read-only data structure consisting of lists of ...
1
vote
0answers
43 views

Is there a polynomial time algorithm for Poly-trees (Oriented trees) isomorphism?

In terms of graph isomorphism complexity classes Trees have a polynomial time algorithm and Directed Acyclic Graphs (DAG's) do not (so far). What about Poly-trees (oriented trees)? These are DAG's ...
1
vote
0answers
95 views

Analogue break down between complexity theory and computability theory

Motivated by my post, Is there a program for theory of incompleteness in NP, much of NP-completeness theory has been heavily influenced by computability theory for which we were successful in proving ...
4
votes
0answers
193 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 ...
2
votes
0answers
118 views

Polynomial-time algorithm solving approximately a generalization of the travelling salesman problem

Take a graph $G$ and a number of sets of nodes of $G$. The problem is to find the shortest path passing through at least one node in each node set. If each node set consists of only one node, the ...
8
votes
1answer
112 views

Computing a transversal of a subgroup $H$ of $G$ in expected $O(|G : H|^2 \log |G : H| + |H|)$ time

I have the book "Handbook of Computational Group Theory", by Derek Holt, and in it is a section on finding the transversal of a subgroup. Recall a transversal of a subgroup $H$ of $G$ is a single ...
7
votes
2answers
144 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 ...
0
votes
2answers
226 views

Relation between P and FP

For a decision problem that belongs to P can we assume that the equivalent function problem belongs to FP? For example: Is 8 a primal number? Belongs to P means that Find a primal number belongs to ...
49
votes
9answers
6k views

The “sensitivity” of 2-colorings of the d-dimensional integer lattice

Consider the $d$-dimensional integer lattice, $Z^d$. Call two points in $Z^d$ "neighbors" if their Euclidean distance is 1 (i.e., if they differ by 1 on exactly one coordinate). Let $C$ be a ...
4
votes
0answers
167 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
0answers
187 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
1answer
183 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)= ...
2
votes
1answer
173 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
0answers
114 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. ...
1
vote
0answers
83 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 ...
1
vote
1answer
168 views

Construction of an integral point set given the set of distances, its minimal description to get a measure of its complexity and its unique identifier

Given a set of distances between every pair of points of an integral point set $P$ of $n$ points; say $D = \{{d_i}\}$. Q1. What is the least time complexity possible/known for recreating the ...
11
votes
1answer
470 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 ...
4
votes
2answers
771 views

Efficient algorithms to determine the roots of: $p(x) = r^x $ in the finite field $GF(q)$, where $r$ a primitive root of the field

I need to make sure that no efficient (i.e., polynomial time) algorithm exists for the following problem: Exponentiating Polynomial Root Problem (EPRP) Let $p(x)$ be a polynomial with $\deg(p) \geq ...
4
votes
1answer
216 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 $$ ...
1
vote
0answers
56 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 ...
11
votes
2answers
839 views

Which recursively-defined predicates can be expressed in Presburger Arithmetic?

In Presburger Arithmetic there is no predicate that can express divisibility, else Presburger Arithmetic would be as expressive as Peano Arithmetic. Divisibility can be defined recursively, for ...
1
vote
2answers
195 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
0answers
60 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 ...
26
votes
19answers
3k views

What is the easiest randomized algorithm to motivate to the layperson?

When trying to explain complexity theory to laypeople, I often mention randomized algorithms but seemingly lack good examples to motivate their usage. I often want to mention primality testing but ...
9
votes
2answers
982 views

An algorithm to find non-trivial linear dependencies

This question is inspired by another MO question about special stratifications of equivariant Grassmannians, that turned out to be a problem of computing non-trivial circuits in a vector matroid. To ...
0
votes
0answers
91 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
1answer
100 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
1answer
72 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
1answer
83 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 ...
2
votes
0answers
110 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 - ...
0
votes
1answer
101 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
1answer
339 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 ...
6
votes
0answers
88 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 ...