Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [big-picture]

The big picture tag is for a "broad, overall view or perspective of an issue or problem."

1
vote
1answer
371 views

Possible to do Complexity theory with only counting and Pigeonhole

Most of the proofs in the book Computational complexity by Barak and Arora seem to be Pigeonhole in disguise. What are some places in Complexity theory where counting and Pigeonhole was insufficient ...
1
vote
0answers
98 views

What definition for $FPT$ algorithm for $KSUM$ gives $W[P]=FPT\implies KSUM$ is $FPT$?

In the definition on $KSUM$ problem we are given $n$ input integers and we have to decide if $K$ of them sum to $0$. $KSUM$ is $FPT$ if there is a $O(f(K)poly(n))$ algorithm for it. However Downey ...
3
votes
0answers
120 views

What are the consequences if $W[i]=W[i-1]$?

$FPT=W[1]$ does not collapse the $W$ hierarchy however falsifies $ETH$ belief. Is there non-trivial consequence if $W[i]=W[i-1]$ and any other consequence at $W[1]$?
1
vote
0answers
36 views

Monotone complexity of PLP

Blum and Nisan show Positive Linear Programming could be done in $NC$ if we only ask for approximate solutions. This paper https://pdfs.semanticscholar.org/8dc7/5aa9d72864022d848c3e599c5f24d9d527e7....
3
votes
0answers
91 views

Does $P=BPP$ say anything about space complexity?

There are many streaming algorithms with sublinear randomized space but linear deterministic space. Does $P=BPP$ have anything to do with derandomizing space and more importantly but not related to ...
5
votes
1answer
206 views

From $PIT\in P$ to $P=BPP$

If $PIT$ has been derandomized then still how far would we be from showing $P=BPP$? What additional barriers need to be climbed?
2
votes
1answer
49 views

Certainty of mutual confirmation over faulty channels?

This is a very theoretical question, although I am sure the problem pops up in lots of IT and automation applications. Still, I prefer to formulate it in an action-movie scenario (a bit of the ...
4
votes
1answer
220 views

The Maxwell's Demon and Computer Science

What is the best source -in terms of quality- that would explain the argument that uses computations concepts to demonstrate that the Maxwell's Demon does not break the second law of thermodynamics? I ...
3
votes
0answers
159 views

Why are one way functions and pseudorandom number generators considered necessary or essential for derandomization?

If strong pseudorandom number generator exists then $BPP=P$ holds and if one way functions exists then $BPP\subseteq SUBEXP$ holds. What are the best statements we have proved that come close to ...
1
vote
4answers
290 views

Is Biological Computation a theme covered by the Theoretical Computer Science?

I want to say computation realized by biological systems themselves. I'm not talking about bio-inspired algorithms, or applications in computation using living systems. This question is more about an ...
0
votes
1answer
90 views

On polytope lattice points

Given a convex polytope let the width of the polytope be $d$ and the farthest euclidean distance between any points in the polytope be $e$. Denote $\mathcal P(a,c)$ to be the set of convex polytopes ...
2
votes
1answer
224 views

Where can I seek help when I cannot understand a research paper? [closed]

Where can I seek help when I cannot understand a research paper? Instead of emailing the author since the paper is long time ago, I am preferring some discussion forum that people exchange ideas on ...
3
votes
0answers
205 views

Is there any known strategy that avoids circuits and that respects believed separations to prove $P$ is not $NP$?

Vinay Deolalikar's approach tried to randomness is not strong enough, Blum's proof tried to show $P/poly$ is not strong enough, Mulmuley's and Smale's approach (while not enough to show $P\neq NP$) ...
1
vote
1answer
159 views

Fixed parameter tractable Integer Programming and $FPP$

Integer programming is $NP$ complete however fixed parameter tractable in number of variables. Is the fixed parameter version in parametrized analogue of $P$-complete or in parametrized analogue of $...
4
votes
0answers
142 views

On status of Valiant's $NC^2=P^{\#P}$ provability program?

In here it is written 'A most interesting/controversial talk was by Leslie Valiant. He explored paths to try to prove that $NC^2=P^{\#P}\dots$'.... This was a decade back. What is the rationale (at ...
4
votes
0answers
156 views

On earlier references for $P=BPP$ and Kolmogorov's possible view on modern breakthroughs involving randomness?

Kolmogorov and Uspenskii in this paper 'http://epubs.siam.org/doi/pdf/10.1137/1132060' speculate P=BPP in 1986. They do this without getting into circuit lower bounds and from a different view which ...
3
votes
1answer
196 views

On $NP$ and $XP$ classes?

On page 33 venn diagram in http://tcs.rwth-aachen.de/~sanchez/slides/Raleigh2014.pdf it is implied that $XP\subseteq NP$. Below this there is a statement which says $XP\not = NP$ unless $P=NP$. Is ...
8
votes
3answers
524 views

What CS theories are absolutely paramount for someone new to TCS to understand? [closed]

First - I'm happy to be a part of this community. Electronics and software engineering are both my passion and my profession, yet I feel as if I'm missing a solid basis in theoretical computer science....
0
votes
0answers
89 views

P=BPP and derandomizing Vazirani-Valiant?

Vazirani-Valiant reduction is a randomized reduction from SAT to unambiguous SAT. Is P=BPP strong enough to derandomize Vazirani-Valiant reduction? If not what other ingredients are necessary to ...
1
vote
1answer
125 views

Unambiguous SAT and sparse languages

What is the consequence if there are only polynomially many 'yes' classes of instances of a language that is polynomial time reducible from a problem equivalent to UnambiguousSAT (such as possibly ...
2
votes
0answers
83 views

On analogies between parallel complexity and polynomial time hierarchy structure?

Is it known $\mathsf{RNC=NC\iff P=RP}$ or $\mathsf{BPNC=NC\iff P=BPP}$? Are there any analogies (such as collapse results, problems which suggest analogies such as gcd(in NC) and factoring (in P), ...
-1
votes
1answer
187 views

Can message passing help in GI related problems?

Can message passing algorithms like those used in https://arxiv.org/pdf/1704.00395.pdf be useful in showing GI testing is in P? Note message passing is prominent in AI and has been tried in decoding ...
5
votes
1answer
412 views

Implications of faster randomized $CIRCUIT SAT$ algorithm

In here on page $13$ proposition $1$ it says 'If $CIRCUIT$ $SAT$ on $n$ inputs and $m$ gates is in $2^{n^{o(1)}}poly(m)$ time, then $EXP\not\subseteq P/poly$'. Can we have randomized $2^{n^{o(1)}}...
5
votes
0answers
158 views

Converse to natural proofs theorem?

Natural proofs paper shows 'if there is a natural property not possessed by any function in P/poly then there is no $2^{n^\epsilon}$-hard PRG'. Is it easy to see the converse 'if there is no $2^{n^\...
2
votes
1answer
124 views

Consequences of faster parameterized integer programming

Integer programming in $k$ variables can be done in $k^{O(k)}$ time and $O(k^c)$ space. Is there any consequence if it can be done in $k^{O(k^\alpha)}$ time and $O(k^c)$ space for some $\alpha\in(0,1)...
6
votes
2answers
308 views

On integer programming

Integer programming is NP-hard. What is the status of integer programming problem that decides between existence of $\leq1$ solution and $>1$ solutions (note $0$ solutions falls in $\leq1$ ...
4
votes
1answer
205 views

Word length using entropy : Maximum entropy criteria

The question is based on research paper titled, Markovian language model of the DNA and its information content In the supplementary document, the Authors show how they determine the word length of ...
0
votes
0answers
79 views

Permanent in Bounded error Quasi Poly time

Is there any consequence to complexity theory if Permanent has a BQP (classical quasipoly version of BPP)? Is there any consequence to complexity theory if Permanent has a QP (classical quasipoly ...
7
votes
2answers
341 views

How powerful is $ACC^0$ circuit class in average case?

We know that $NEXP$ is not in $ACC^0$ . Does the result that $NEXP$ is not in $ACC^0$ also hold in average case? That is given a boolean function in $NEXP$ is it known that for every input length $...
2
votes
2answers
132 views

Collection of failed attempts to solve X

I've been half-jokingly entertaining the idea of trying to blog about "n ways not to solve P vs NP" in the indefinite future, and in my search came across the How not to solve P=NP? question on cs....
40
votes
10answers
15k views

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

Real computers have limited memory and only a finite number of states. So they are essentially finite automata. Why do theoretical computer scientists use the Turing machines (and other equivalent ...
2
votes
1answer
373 views

Is there a problem currently known to be outside class $\mathsf{NP}\cup\mathsf{coNP}$ but inside $\mathsf{BPP}$?

May be this is trivial but I do not know the answer. As far as we know $$\mathsf{BPP}\subseteq\mathsf{\Sigma}_2\cap\mathsf{\Pi}_2$$ holds. As far as we know $$\mathsf{NP}\cup\mathsf{coNP}\subseteq\...
5
votes
1answer
162 views

Implications of a recent negative result to geometric complexity

A paper was posted in arxiv http://arxiv.org/pdf/1512.03798.pdf titled 'Rectangular Kronecker coefficients and plethysms in geometric complexity theory' by Christian Ikenmeyer and Greta Panova with ...
3
votes
2answers
291 views

Consequences of $NP\subseteq P/poly$ to $BQP$

A post here Consequences of $BQP \subseteq P/poly$? queried on Consequences of $BQP \subseteq P/poly$. It is not known if $NP\subseteq BQP$. In general, what are the consequences of $NP\subseteq P/...
8
votes
2answers
251 views

Uncertainties in GCT program

In https://en.wikipedia.org/wiki/Geometric_complexity_theory it is mentioned that ".. Ketan Mulmuley believes the program, if viable, is likely to take about 100 years before it can settle the P vs. ...
15
votes
2answers
1k views

Status quo of category theory and monads in theoretical computer science research?

Background. I am a bachelor student who is interested in research related to category theory, monads and Haskell, and I want to find a topic for my bachelor’s thesis in that area. I have looked at ...
6
votes
1answer
127 views

Lower bounds for nonuniform circuits and oracles separating complexity classes

I have read that Furst, Sax, and Sipser came up with their lower bound for nonuniform AC0 while trying to prove an oracle separation. Can someone explain how proving lower bounds for circuits and ...
3
votes
1answer
326 views

Log Rank Conjecture Collaborative Approach [closed]

Recently a post was made in Mathoverflow seeking possible avenues for collaborative projects. I made a proposal for Log Rank conjecture in https://mathoverflow.net/questions/219638/proposals-for-...
11
votes
2answers
300 views

Consequence of PIT over $\Bbb Z[x_1,\dots,x_n]$ not having efficient algorithm

Given $p(x_1,\dots,x_n),q(x_1,\dots,x_n)\in \Bbb Z[x_1,\dots,x_n]$ such that coefficients of $p,q$ are bounded by $B$, does $p\equiv q$ hold? Schwartz-Zippel lemma applies here since it holds for ...
-2
votes
1answer
224 views

Is there a randomized complexity class analogous to $\mathsf{P/Poly}$?

$\mathsf{P/Poly}$ captures those problems that could be solved in polynomial time given some precomputed polynomial number of constants. Is there an analogous complexity class in randomized world ...
1
vote
0answers
55 views

Analogues of different complexity classes in various models

We suspect following relation: $$TC^0\subsetneq NC^1\subsetneq L\subsetneq NL\subsetneq AC^1\subsetneq NC^2\subsetneq P\subsetneq NP\subsetneq PH\subsetneq PSPACE$$ in Turing/boolean circuit ...
-2
votes
1answer
106 views

what can be said about complexity of “typical” supercomputing programs/ applications? any NP hard?

supercomputers have risen dramatically in their computational powers last few decades due to Moore's law & also increasing parallelism technology in hardware and software. many different types of ...
4
votes
1answer
342 views

Analogies between VNP and NP

Valiant introduced the class VNP with respect to "arithmetic circuits" over 35 years ago in a "rough" analogy to NP. Recently, there have been major advances in the area of arithmetic circuits eg as ...
-2
votes
1answer
181 views

A trivial question on hierarchy [closed]

According to wiki we know that $\mathsf{ACC^0\subseteq TC^0\subseteq NC^1\subseteq L\subseteq P\subseteq NP\subsetneq NEXPTIME}.$ Class $\mathsf{ACC^0}$ is included in $\mathsf{TC^0}$ is in http://en....
5
votes
1answer
1k views

Why study type theory?

After reading the literature on type theory (especially the constructive kind - CTT) I'm left wondering "why" should one study type theory, specifically within the confines of "computing" in general? ...
3
votes
3answers
328 views

Distinguishing semantics vs syntactic techniques and the syntax of your semantic domains

Consider a denotational semantics from simply-typed $\lambda$-calculus into dependent type theory. Is that actually a (trivial) term transformation into that dependent type theory? After all, type ...
13
votes
1answer
1k views

Why was there a need for Martin-Löf to create intuitionistic type theory?

I've been reading up on Intuitionistic Type Theory (ITT) and it does make sense. But what I'm struggling to understand is "why" was it created in the first place? Intuitionistic Logic (IL) and Simply-...
6
votes
2answers
534 views

How would a theory of computation course that culminated in lambda-calculus as “the” model of computation, instead of Turing machines, look like?

Currently, our ToC (Theory of Computation) courses are designed with the following progression of topics: Finite automata and regular languages Pushdown automata and context-free languages Turing ...
7
votes
2answers
353 views

possible bridge between group growth theory and complexity theory?

RJ Lipton conjectures a link between group growth theory and complexity theory. Group growth theory has undergone rapid advance in the last decade and has many surface similarities/ parallels with ...
3
votes
3answers
468 views

Why is lambda calculus so “function” oriented?

I've always had this question nagging at me subconsciously but have never been able to intuitively grasp it. Why does $\lambda$-calculus have a functional notation? Why is everything a function? It ...