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)

-2
votes
0answers
24 views

How would one describe the rules of Pascal's triangle (which gives us the “normative curve” of probability) in cellular automata terms? [on hold]

If cellular automata simple rules can create complex structures, then how pascal's triangle can be explain as these rules as they are so symmetric ?? For example, elementary cellular automata rule ...
-2
votes
0answers
43 views

are signs of coefficients arbitrary in 01-integer programming? [on hold]

looking to understand more about full coverage integer programming i wondered if my research should include forms of the problem with the possibility for negative coefficients i went looking for an ...
0
votes
0answers
62 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 ...
0
votes
0answers
21 views

Arithmetical complexity of substitution method for solving systems of linear equations [closed]

Let us have a system of linear equations (say m equations, n variables, over the reals, perhaps just m=n). How many basic operations in the reals do we need to perform to solve the system by the ...
3
votes
1answer
80 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 ...
1
vote
0answers
63 views

Efficient realization of a restricted neighborhood hypergraph

In a graph $G$, the (open) neighborhood of a vertex $v$ is the set of vertices adjacent to $v$ (so vertex $v$ is excluded). The neighborhood hypergraph of $G$, denoted by $\mathcal{N}(G)$, is a ...
5
votes
0answers
101 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
28 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. ...
17
votes
0answers
493 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 ...
1
vote
0answers
98 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
215 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 ...
3
votes
0answers
41 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
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 ...
2
votes
1answer
63 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 ...
0
votes
0answers
24 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
17 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
40 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
48 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
99 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 ...
6
votes
1answer
147 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 ...
8
votes
1answer
115 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 ...
2
votes
0answers
122 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 ...
7
votes
2answers
147 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
0answers
197 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 ...
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
1answer
174 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
116 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
0answers
192 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
0answers
89 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
1answer
482 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
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 ...
1
vote
0answers
57 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
2answers
208 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
61 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
1answer
186 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
0answers
94 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
102 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
74 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 ...
2
votes
1answer
99 views

Connection between Barnette conjecture and hardness of cubic graph decomposition

Motivated by this post on cubic graphs decompositions and the connection to Barnette's conjecture, I am interested in decomposing a connected bridgeless cubic graph into edge-disjoint paths of length ...
0
votes
1answer
102 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
343 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
0answers
111 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
0answers
89 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
1answer
402 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
1answer
216 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) ...
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
1answer
202 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
0answers
71 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
0answers
72 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
2answers
211 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 ...