September 18, 2009 by kintali

A Generalization of Erdos’s Proof of Bertrand-Chebyshev Theorem

Bertrand’s postulate states that for every positive integer n, there is always at least one prime psuch that n < p < 2n. This was proved by Chebyshev in 1850, Ramanujan in 1919 and Erdos in 1932.

Legendre’s conjecture states that there is a prime number between n² and (n+1)² for every positive integer n. It is one of the four Landau’s problems, considered as four basic problems about prime numbers. The other three problems are

Goldbach’s conjecture : Every even integer n > 2 can be written as the sum of two primes ?
Twin prime conjecture : There are infinitely many primes p such that p+2 is prime ?
Are there infinitely many primes p such that p-1 is a perfect square ?

All these problems are open till date !! Lets look at the following generalization of the Bertrand’s postulate :

Does there exist a prime number p, such that kn < p < (k+1)n for all integer n>1 and k <=n ?

A positive answer for k = n would prove Legendre’s conjecture. Recently I generalized Erdos’s Proof of Bertrand-Chebyshev’s Theorem and proved the following theorem :

Theorem : For any integer 1 < k < n, there exists a number N(k) such that for all n >=N(k), there is at least one prime between kn and (k+1)n.

Like Erdos’s Proof, my generalization uses elementary combinatorial techniques without appealing to the prime number theorem. An initial draft is available on my homepage.

I have the following question :

Are there infinitely many primes p such that p+k is prime ?

Is the answer known for any fixed k > 2 ? What if k is allowed to depend on p ? If you know any papers addressing such questions, please leave a comment.

September 7, 2009 by kintali

Random Restriction and Circuit Lower Bounds

The class \aczero\ consists of all uniform families of circuits of constant depth and polynomial size, with unlimited-fanin AND and OR gates. NOT gates are allowed only at the inputs. The class \saczero\ is the semi-unbounded version of \aczero\ i.e., AND gates have constant fan-in.

The class $AC^0$ consists of all uniform families of circuits of constant depth and polynomial size, with unlimited-fanin AND and OR gates. NOT gates are allowed only at the inputs. The class $SAC^0$ is the semi-unbounded version of $AC^0$ i.e., AND gates have constant fan-in. In the class $NC^0$ both AND and OR gates have constant fan-in. The following strict hierarchy is known.

For all prime numbers $p$ , $NC^0 \subsetneq SAC^0 \subsetneq AC^0 \subsetneq AC^0[p] \subsetneq TC^0$ .

Todays post is is about the following theorem.

Theorem : $SAC^0 \subsetneq AC^0$

Proof : $AC^0$ is closed under complementation and $SAC^0$ is not.

Exercise : Prove that $SAC^0$ is not closed under complementation.

Recently I came up with an alternate proof of the above theorem using the technique of random restriction of Furst, Saxe and Sipser [FSS’81]. I think my proof can be given as a cool homework problem in introductory complexity theory course. Here it goes…..

Let $G(V,E)$ be a directed simple graph (i.e., $G$ does not have self-loops or multi-edges) with $|V|=n$ and $|E|=m$ . Let $indegree(v)$ represent the indegree of a vertex $v \in V$ . Motivated by cycle languages, we define the language $Positive Indegree$ as follows :

$Positive Indegree$ = $\{ <G(V,E)>\ |\ indegree(v)\ \geq\ 1\ \forall\ v\ \in\ V\}$ .

$G$ is represented as $(x_1,y_1),\dots,(x_m,y_m)$ where each $x_i$ and $y_i$ is in $\{1,2,\dots,n\}$ encoded as binary strings. The meaning of $(x,y)$ is that there is a directed edge from $x$ to $y$ . We may assume that circuits computing $Positive Indegree$ will have $m = O(n^2)$ binary inputs in a prespecified order.

Exercise : $Positive Indegree \in AC^0$ .

Lemma : If a CNF or a DNF computes $Positive Indegree$ , then

each term includes at least $n-1$ variables, and

there are at least $n$ terms.

Hence there is no $SAC^0$ circuit of depth two for $Positive Indegree$ .

Proof : We will prove this lemma for CNFs. The proof for DNFs is similar. Let $\mathcal{C}$ be a CNF circuit computing $Positive Indegree$ .

Assume that $\mathcal{C}$ has some term $t$ that depends on less than $n-1$ variables. Then when all inputs to $t$ are 0, $t$ outputs 0 and hence $\mathcal{C}$ outputs 0. Consider the graph $H$ consisting of a cycle on $n-1$ vertices (say $v_1,\dots,v_{n-1}$ ) and an isolated vertex $v_n$ . Note that $H \notin Positive Indegree$ . Let $H_i$ be the graph obtained by adding the edge $(v_i,v_n)$ to $H$ . Now $H_i \in Positive Indegree$ for $1 \leq i \leq n-1$ . If $t$ does not depend on all variables of the form $(v_i,v_n)$ then $\mathcal{C}$ outputs 0 for some $H_i$ , which is a contradiction.

Consider the graph $F^i$ consisting of a cycle on $n-1$ vertices (these are the vertices from $v_1,\dots,v_{n}$ except $v_i$ ) and an isolated vertex $v_i$ . $\mathcal{C}$ must output zero on $F^i$ for $1 \leq i \leq n$ . $\mathcal{C}$ outputs 0 only when one of the terms (OR gates) outputs zero. But each OR gate outputs 0 on exactly one assignment of the input variables, Hence, $\mathcal{C}$ must have at least $n$ terms.

Restriction : Let $\mathcal{C}$ be a circuit computing $Positive Indegree$ . Setting an input of $\mathcal{C}$ to 0 (resp. 1) corresponds to deleting (resp. contracting) the corresponding edge from the input graph $G$ .

Observation : If some of the inputs of $\mathcal{C}$ are restricted to 0 or 1, the resulting circuit still computes $Positive Indegree$ , albeit on a smaller graph.

Theorem : $Positive Indegree \notin SAC^0$ .

Proof : We assume that there is an $SAC^0$ circuit (say $\mathcal{C}$ of some constant depth $d$ ) computing $Positive Indegree$ and derive a contradiction. Using the random restriction technique of [FSS’81] we squash $\mathcal{C}$ down to depth $d-1$ while still computing $Positive Indegree$ on many variables. This squashing still preserves the constant fanin of AND gates. We repeat this method $d-2$ times to obtain an $SAC^0$ circuit of depth 2 with constant AND fanin, which contradicts the previous lemma.

Corollary : $SAC^0 \subsetneq AC^0$ .

References :

[FSS’81] Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. In FOCS, pages 260–270, 1981.

September 1, 2009 by kintali

Relativization Barrier

I am back in Atlanta after attending an awesome Barriers Workshop. This workshop is mainly about the barriers in resolving P vs NP problem and possible techniques to overcome these barriers. It is a five day workshop covering circuits lower bounds, arithmetic circuits, proof complexity, learning theory and pseudo-random generators. I enjoyed every talk and panel discussions. Everybody seemed very positive that $P \neq NP$ .

Today’s post is a quick introduction to Relativization Barrier. I will write separate posts about natural proofs and algebrization barriers soon. Relativization Barrier is one of the first barriers we learn in an introductory graduate level complexity course.

In relativized world we grant the Turing machine M the access to an oracle that could compute some function A in a single time step. Such a machine, called oracle TM, computes relative to A, is represented by $M^A$ . Oracle TMs are used in Turing-reducibility, a generalization of mapping-reducibility.

The method of diagonalization relativizes i.e., any separation result in the real world, proved using diagonalization, extends to the relativized world. Baker, Gill and Solovay [BGS’75] showed that there exists oracles A and B for which $P^A$ and $NP^A$ are provably different and $P^B$ and $NP^B$ are provably equal. That is P vs NP has different answers in different worlds !! Hence techniques such as diagonalization, cannot be used to resolve P versus NP.

Theorem : An oracle A exists such that $P^A \neq NP^A$ . An oracle B exists such that $P^B = NP^B$ .

Let B be any PSPACE-complete problem. We have $NP^B \subseteq NPSPACE \subseteq PSPACE \subseteq P^B$ . The first and third containments are trivial and the second containment follows from Savitch’s theorem. Hence $P^B = NP^B$ . Constructing A is a non-trivial task. Look at Sipser’s book (page 350) for details of constructing A.

Therefore any solution to the P versus NP problem will require non-relativizing techniques i.e., techniques that exploit properties of computation that are specific to the real world i.e., techniques that analyze the computations not just simulate them.

References :

[BGS’75] T. Baker, J. Gill, and R. Solovay : Relativizations of the P=?NP question. SIAM J. Comput., 4:431–442, 1975.

Baker, Gill and Solovay [BGS’75] showed that techniques such as diagonalization,

cannot be used to resolve P versus NP. Such techniques would work in [relativized]

world, where both P and NP machines could compute some function

f in a single time step.

However, there are some relativized

worlds where P = NP, and other relativized worlds

where P != NP. Therefore any solution to the P versus NP

problem will require non-relativizing techniques i.e., techniques

that exploit properties of computation that are specific to

the real world.

My Brain is Open

Computational Complexity, Polyhedral Combinatorics, Algorithms and Graph Theory

Month: September 2009

A Generalization of Erdos’s Proof of Bertrand-Chebyshev Theorem

Random Restriction and Circuit Lower Bounds

Relativization Barrier

Share this:

Share this:

Share this: