Questions tagged [big-picture]

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

Filter by
Sorted by
Tagged with
22
votes
5answers
3k views

Implications of unprovability of $P\neq NP$

I was reading "Is P Versus NP Formally Independent?" but I got puzzled. It is widely believed in complexity theory that $\mathsf{P} \neq \mathsf{NP}$. My question is about what if this is not ...
1
vote
3answers
319 views

what is a model of computation, mathematically? [closed]

Where can I find a mathematical definition for "model of computation"? https://en.m.wikipedia.org/wiki/Model_of_computation doesn't provide a precise definition for "model of computation"--it doesn't ...
4
votes
1answer
188 views

Qubit gates in google supremacy

The gates in quantum supremacy experiment are nearest-neighbor and have spatial locality. Would this additional information help bolster IBM's argument to perhaps simulate quantum supremacy experiment ...
9
votes
1answer
286 views

Evidence for $\mathsf{P} \neq \mathsf{PP}$ if the polynomial hierarchy collapses?

We think that $\mathsf{PH}$ does not collapse, and that $\mathsf{PP}$ is not in $\mathsf{P}$. Suppose on the contrary that $\mathsf{PH}$ does collapse, say even $\mathsf{P}= \mathsf{NP}$. $\mathsf{...
40
votes
3answers
5k views

Evidence that matrix multiplication is not in $O(n^2\log^kn)$ time

It is commonly believed that for all $\epsilon > 0$, it is possible to multiply two $n \times n$ matrices in $O(n^{2 + \epsilon})$ time. Some discussion is here. I have asked some people who are ...
0
votes
0answers
168 views

On PP in communication complexity

Aho says $D(f)=O(N(f)N(\overline f))$ where $D(f)$ is deterministic communication complexity and $N(f)$ is non-deterministic version. Do we know $PP(f)=\Omega(2^{(N(f)N(\overline f))^{O(1)}})$ or $...
1
vote
0answers
170 views

P=BPP and derandomizing Vazirani-Valiant?

Vazirani-Valiant reduction is a randomized reduction from $SAT$ to unambiguous $SAT$. 1. Is $P=BPP$ strong enough to derandomize Vazirani-Valiant reduction? 2. If not what other ingredients are ...
7
votes
0answers
189 views

Geometric Intuition behind Locally testable codes

Conventional coding theory provides a good geometric picture behind linear error correction codes in terms of Hamming distance. What additional geometric requirement one should add to make a code ...
9
votes
3answers
432 views

Why exactly are complexity theorists interested in closed timelike curves?

Context: There are several papers that study the implications of closed timelike curves (CTCs) to quantum complexity. In 2008, Aaronson and Watrous published their famous paper on this topic which ...
2
votes
1answer
128 views

Lower bound on alternations needed in $BQP$ versus $PH$ result?

What is the fastest $f(n)$ the relatively new result of oracle separation of $\mathsf{BQP}$ from $\mathsf{PH}$ provides such that ${\#\mathsf{SAT}}\not\subseteq\mathsf{FP}^{\mathsf{PH}[O(f(n))]}$ ...
1
vote
0answers
122 views

Is Combinatory Logic (CL) still relevant for programming language theory?

I've been reading up on R. Smullyan's "To Mock a Mockingbird" and Hindley's "Lambda-Calculus and Combinators: An Introduction". I've even read Schonfinkel's 1924 paper introducing the idea of ...
9
votes
1answer
607 views

What is the “question” that programming language theory is trying to answer?

I've been interested in various topics like Combinatory Logic, Lambda Calculus, Functional Programming for a while and have been studying them. However, unlike the "Theory of Computation" which ...
68
votes
13answers
19k views

Uses of algebraic structures in theoretical computer science

I'm a software practitioner and I'm writing a survey on algebraic structures for personal research and am trying to produce examples of how these structures are used in theoretical computer science (...
1
vote
0answers
248 views

On $BPP$ in $P^{NP}$ and $SETH$

It is believed showing $BPP$ in $P$ involves good $PRG$s and faces lower bound barriers. Does showing $BPP$ in $P^{NP}$ which would mean $BPP\neq EXP^{NP}$ face similar $PRG$ and give lower bounds? ...
4
votes
0answers
117 views

Dequantumizability known and unknown?

Dequantumizable problems have been taking some headlines these days (for example https://www.scottaaronson.com/blog/?p=3880 and https://www.quantamagazine.org/teenager-finds-classical-alternative-to-...
67
votes
7answers
3k views

Which interesting theorems in TCS rely on the Axiom of Choice? (Or alternatively, the Axiom of Determinacy?)

Mathematicians sometimes worry about the Axiom of Choice (AC) and Axiom of Determinancy (AD). Axiom of Choice: Given any collection ${\cal C}$ of nonempty sets, there is a function $f$ that, given a ...
61
votes
5answers
5k views

The origin of the notion of treewidth

My question today is (as usual) a bit silly; but I would request you to kindly consider it. I wanted to know about the genesis and/or motivation behind the treewidth concept. I sure understand that ...
4
votes
0answers
83 views

Fixed dimension Linear Integer Programming in $NC$

We know if fixed dimension linear integer programming is in $NC$ then integer $GCD$ is in $NC$. Is this the only non-trivial implication of fixed dimension linear integer programming in $NC$?
2
votes
1answer
433 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 ...
3
votes
2answers
237 views

Discerning the best model for a problem

This is a vague question. I will do my best, I think it has definite answers. I am hoping for answers of the form "Read book x, learn this specific topic, read this paper/s". What is bothering me is ...
0
votes
0answers
112 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
133 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
37 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
100 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
240 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?
9
votes
3answers
476 views

Benefits for syntactic and semantic classes

This is a post separated from Consequences of UP equals NP, and also a follow-up question to Semantic vs. Syntactic Complexity Classes. In the above post we learned about the semantic and syntactic ...
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 ...
1
vote
4answers
310 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 ...
3
votes
0answers
184 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 ...
4
votes
1answer
245 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 ...
42
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 ...
0
votes
1answer
128 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
229 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
210 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
187 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
146 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 ...
5
votes
0answers
270 views

Sketch of Razborov's paper “On the method of approximations”

(The following question has bothered me for many years.) Razborov seems to have obtained some of the strongest/award winning lower bounds on circuits found in the field over many years, largely ...
4
votes
0answers
170 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 ...
2
votes
1answer
223 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 ...
41
votes
4answers
2k views

Why have we not been able to develop a unified complexity theory of distributed computing?

The field of distributed computing has fallen woefully short in developing a single mathematical theory to describe distributed algorithms. There are several 'models' and frameworks of distributed ...
86
votes
7answers
28k views

What is the contribution of lambda calculus to the field of theory of computation?

I'm just reading up on lambda calculus to "get to know it". I see it as an alternate form of computation as opposed to the Turing Machine. It's an interesting way of doing things with functions/...
7
votes
3answers
586 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....
1
vote
1answer
141 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
89 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
191 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
420 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)}}...
4
votes
1answer
235 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 ...
5
votes
0answers
160 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^\...
7
votes
2answers
368 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
1answer
130 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)...