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)

3
votes
1answer
194 views

counting patterns in a word

Do algorithms exist to find all the patterns in a word? I would like to count all the 3-step increasing sequences (123 i.e. 123, 234 & 345) in some word in the alphabet {1,2,3,4,5} such as ...
6
votes
1answer
313 views

compression of a Turing machine run sequence

consider a Turing machine with a set of states $s_n$ and alphabet symbols $a_n$. now consider a "run sequence" generated from a starting input in the following sense. the run sequence is defined as ...
1
vote
0answers
214 views

Multiobjective semidefinite programming

Let $C$ be size $n \times n^{2}$. Let $B$ be size $2^{g(n)} \times n^{2}$ where $g(n) > n$. There is only one $\mathcal{1}$ per row of $C$ and remaining entries of $C$ are $\mathcal{0}$. $B$ is ...
3
votes
1answer
160 views

bounding the probability that a polynomial is near 0

Given a polynomial $p(x_1,\ldots, x_k)$ in $k$ variables with maximum degree $n$, and $x_1,\ldots, x_k \in [0,1]$. Suppose $\max_{x \in [0,1]^k} p(x) = 1$, can we get an upper bound on the probability ...
4
votes
1answer
412 views

Complexity of computing expansion of a newform level 18 weight 3 and character [3] - OEIS A116418

I am not familiar with newforms, so this may not make any sense. OEIS sequence A116418 is Expansion of a newform level 18 weight 3 and character [3] Numerical evidence suggest that up to $10^5$ $$ ...
4
votes
1answer
502 views

Lovász $\delta$ condition for LLL Algorithm

http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm What is the importance of the $\delta$ parameter for LLL bases called Lovász condition? ...
1
vote
0answers
518 views

How to solve simple bilinear equations under extra linear constraints

Hello, This is the full version of a question I asked earlier. I am trying to understand whether finding a solution to the following bilinear system is computationally hard or easy: $\lambda_i^T ...
3
votes
0answers
276 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
3answers
667 views

Problem regarding subsets that sum to 0

Let $X=\{x_1,...,x_n\}$ be a multiset of $n$ real numbers, and let $x_1+\dots+x_n = 0$. Is there a way to find the maximum number of unique subsets any $X$ can have given $n$, such that each subset ...
4
votes
1answer
617 views

Algorithmic war

No, not the war on drugs, but the game of War considered in Does War have infinite expected length? As noted in that discussion, the game of war can go on forever, but my question is: can it be ...
1
vote
0answers
442 views

Representing vertices of a cube using linear combination of tensor product of smaller cubes

Let $n,N \in \mathbb{N}$ with $N \ge n^{2}$. Let $F[i] = \square[i]$ refer to the cube which has vertices from $\{-1,0,1\}^{n^{i}}$ ($n^{i}$ tuple of alphabets from $\{-1,0,1\} = \square[0] = F[0]$) ...
0
votes
2answers
208 views

equivalence of NL Definitions

Hi, How to prove that the two definitions of the complexity class NL are equivalent. 1st definition is with a non deterministic logspace TM, and the second is with a deterministic logspace verifier ...
7
votes
2answers
329 views

Ordinals and complexity classes

What is the least recursive ordinal $\alpha$ such that there is no algorithm in complexity class $\mathsf{P}$ which implements a well-ordering of $\mathbb{N}$ with order type $\alpha$? (where the size ...
7
votes
2answers
833 views

Distribution of the computable numbers on the real number line

If we order all the positive computable real numbers $r_1,r_2,r_3...$ by their Kolmogorov complexity in some language $L$, then make a histogram plot of the $r_i$ on the real line, and we scale it ...
5
votes
2answers
402 views

Complexity of Membership-Testing for finite abelian groups

Consider the following abelian-subgroup membership-testing problem. Inputs: A finite abelian group $G=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}$ with ...
2
votes
2answers
622 views

Enumerating all Hamiltonian Cycles in a Bipartite Vertex Transitive Graph

Hi everyone! This is my first post, apologies if I made any mistakes anywhere. Here goes the question: Consider all length 7 binary sequences. Let $X$ be the set of sequences with hamming weight 3 ...
1
vote
1answer
269 views

A regular n,2d graph is a good expander.

Context Reading about Expanders Setup A regular n,2d graph is generated as follows: generate d random permutations of [n] connect the edges; giving a n,2d regular graph ...
5
votes
1answer
994 views

Stochastic Matrix: Second largest eigenvalue and second largest absolute value of eigen value

Setup Let $A$ be a stochastic matrix. Let the eigenvalues of $A$ be $1 = \lambda_1 \geq \lambda_2 \geq \lambda_3 ... \geq -1$. Let $\lambda = \max_{x: x \perp 1} \frac{||Ax||}{|| x ||}$ Question: ...
2
votes
1answer
118 views

Structure of class P

Hi all, 1. Has there been any work done on trying to distinguish between different Polynomial Time Hierarchies say, O(n) vs O(n^2) problem? May be Turing Machine is too general for that. May be the ...
6
votes
2answers
375 views

Complexity of detecting a convex body in $\mathbb{R}^n$?

Let $K_0$ be a bounded convex set in $\mathbb{R}^n$ within which lie two sets $K_1$ and $K_2$. $K_0,K_1,K_2$ have nonempty interior. Assume that, $K_1\cup K_2=K_0$ and $K_1\cap K_2=\emptyset$. The ...
11
votes
6answers
1k views

Compressing Graphs (Kolmogorov complexity of graphs)

What is known about compressing graphs? Here, with "compressing", I mean something like "putting a graph into a zip program"; or with a more technical expression, what is know about the Kolmogorov ...
10
votes
1answer
503 views

Complexity of a weirdo two-dimensional sorting problem

Please forgive me if this is easy for some reason. Suppose given $S$, a set of $n^2$ points in $\mathbb{R}^2$. I want to choose a bijective map $f$ from $S$ to the set of lattice points in $\lbrace ...
12
votes
1answer
2k views

Evidence for integer factorization is in $P$

Peter Sarnak believes that integer factorization is in $P$. It is a well-known open problem in TCS to identify the real complexity class of integer factorization. Take a look at this link for Peter ...
1
vote
1answer
219 views

Pseudorandom Generator vs Constant Depth Circuits / Branching Programs

Hi. I am looking for a survey on the state of the art in pseudorandom generators vs (1) constant depth circuits and/or (2) Branching Programs For (1), is "Anindya De, Omid Etesami, Luca Trevisan ...
1
vote
1answer
485 views

P vs NP and OWFS

It is known (simple HW exercise) that: If P = NP, that OWFs (one way functions) can not exist. It is also known that there is a Universal OWF: namely, there is a function f: s.t. if any OWF ...
2
votes
0answers
166 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 ...
4
votes
1answer
712 views

Finding a vertex of least distance to all other vertices in a graph

Some background to my question: if $G$ is a (simple) graph of $N$ vertices, labelled by integers $0,1,...,N-1$, the closeness centrality of a vertex $i$, denoted by $C(i)$, is defined to be the ...
4
votes
1answer
276 views

Hermit H-machines

I call an H-machine a machine that can be connected to turing machines and that takes as input a natural integer n and instantly returns the n'th digit of the mathematical constant H. Is there a ...
0
votes
0answers
132 views

Bounds on reducing from NP to SAT

Let M be a non deterministic turing machine. Suppose M is a TM that runs in T(n) time. Given an instance of x in {0,1}^n, and the question M(x) accepts? We can 1) convert M into an oblivious TM ...
0
votes
0answers
164 views

Survey on the Power of Non-Uniformity

Non-Uniformity is quite powerful in complexity theory. For example: BPP is a subset of P/poly. If NP is a subset of P/poly, then the polynomial hierarchy collapses to Sigma^2. Question: Is there a ...
1
vote
3answers
207 views

Inequality involving size of nodes & min degree of graph.

Context: http://www.sciencedirect.com/science/article/pii/S0019995882904776 Lemma 1 on 3rd page. Question excerpted / rewritten as follows: (V,E) = a graph on {0,1}^n, where there is an edge ...
4
votes
0answers
158 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 ...
2
votes
0answers
108 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 ...
4
votes
1answer
650 views

Turing machines that always halt

Needed for this paper: Here is a possibly more clear version of my question. A Turing machine (with $1$ tape) has sets of tape letters $Y$, state letters $Q$, two symbols $\alpha$ and $\omega$ that ...
2
votes
1answer
277 views

Tail Bound on Binomial

Context: circuit complexity argument: How do I show that $$\sum_{i=0}^{n/2- \sqrt{n}} {n \choose i} \geq 2^n/50$$ ? (as n goes to infinity) [This shows up in proving Mod2 is not in ACC(3)]. ...
0
votes
0answers
118 views

Approximate Solving Linear Equations

EDIT: RESOLVED. Given: $$ x, \{r_i\}_{i=1}^m \in \{0,1\}^n$$ $$ \Pr_{i} [b_i = c \cdot x_i] \geq 1/2 + \epsilon $$ We are given: $$(b_i, r_i)$$ Question: can we in polynomial time find an ...
1
vote
2answers
233 views

Pseudorandom Functions / Pseudorandom Permutations

I'm reading Yao's unpredictability -> pseudorandomness construction and Goldreich/levin's pseudorandom permutation -> pseudorandom generator construction. My question is: is there a direct way to ...
0
votes
2answers
200 views

Formal verification in complexity theory

Reading books and papers on complexity theory, I am struck by the extreme degree to which proofs are stated in an intuitive, hand-wavy way. The alternative is to give a lot of details about the coding ...
3
votes
2answers
319 views

Has Oracles actually provided intuition for proving anything in Complexity Theory?

[EDIT: I realize this question is soft. I realize some people want to close this question. The goal here is trying to answer the following question: So I see these research papers that provide papers ...
1
vote
1answer
304 views

Open?: Bpp VS EXP^NP

Known: BPP vs NEXP is open. BPP is strict subset of EXP^EXP. Question: Is BPP vs EXP^NP open? If so, is there any class between EXP^NP, EXP^EXP concerning which vs BPP it's still open? Thanks! ...
9
votes
1answer
557 views

Polynomial-time complexity and a question and a remark of Serre

My question is about the theory of complexity, but let me first explain my motivation, which comes from number theory or more precisely from trying to understand a question/conjecture of Serre and a ...
3
votes
1answer
185 views

Oracle Separation Results: A^O != B^O yet A = B ?

I know that there exists classes $A$ and $B$ such that: $A^{O_1} = B^{O_1}$, $A^{O_2} != B^{O_2}$. Now, this is my question: do we know of any classes $A$ and $B$ such that $A=B$, yet there is an ...
7
votes
3answers
620 views

Definition of relativization of complexity class

Is there any general definition, for a class $C$ of languages, what is the relativized class $C^A$ for an oracle $A$? Usually, these classes and their relativizations seem to be defined in an ad-hoc ...
1
vote
0answers
178 views

Inherent complexity of a language — when does it exist?

For a language $L$, you can talk about the complexity of a Turing machine $M$ which decides $L$. Can you talk about the time complexity of the language $L$ itself, i.e. say $L$ has complexity $f(n)$ ...
2
votes
2answers
231 views

Oracle Separation Survey

Is there a survey (or a website) somewhere that lists all known separation results? I.e. it has a list of triples: $$ (C_1, C_2, A)$$ where ...
2
votes
0answers
328 views

Hamiltonian paths in subgraphs of rectangular lattice graphs

Is following decision problem NP-hard / NP-complete: Having vertex-induced subgraph of rectangular lattice graph determine if any Hamiltonian path exists Having vertex-induced subgraph of ...
4
votes
2answers
927 views

the complexity of Lanczos method

Hi, all I am working on an algorithm which uses Lanczos method to compute K smallest eigenvalue(and their eigenvectos) of a sparse matrix, just want some information or links about the complexity of ...
2
votes
1answer
179 views

Survey on Structural Complexity

Alot of the proofs I've been recently reading: IP / PSpace / MIP / NEXP / randomized reductions have a certain flavour involving proofs showing equivalence/relation between various complexity ...
6
votes
1answer
235 views

Simplices in convex polytopes

This question is a direct generalization of: Counting the (additive) decompositions of a quadratic, symmetric, empty-diagonal and constant-line matrix into permutation matrices Given a convex ...
0
votes
0answers
89 views

Formal Definition of Random Reducibility

What is the formal definition of Random Reducibility> Arora/Barak is like: "yeah, so it's kind like you take an instance of a problem, create n random instances of the problem; and if you have the ...