Questions tagged [big-picture]
The big picture tag is for a "broad, overall view or perspective of an issue or problem."
41
questions
42
votes
2
answers
4k
views
Semantic vs. Syntactic Complexity Classes
In his "Computational Complexity" book, Papadimitriou writes:
RP is in some sense a new and unusual kind of complexity class. Not any polynomially bounded nondeterministic Turing machine can be the ...
- 16.6k
49
votes
7
answers
8k
views
What constitutes denotational semantics?
On a different thread, Andrej Bauer defined denotational semantics as:
the meaning of a program is a function of the meanings of its parts.
What bothers me about this definition is that it doesn't ...
- 2,707
81
votes
14
answers
24k
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 (...
- 913
50
votes
5
answers
7k
views
Is the Chomsky-hierarchy outdated?
The Chomsky(–Schützenberger) hierarchy is used in textbooks of theoretical computer science, but it obviously only covers a very small fraction of formal languages (REG, CFL, CSL, RE) compared to the ...
- 1,259
33
votes
7
answers
2k
views
Algorithmic lens in the social sciences
Looking at questions through the algorithmic lens (i.e. from an algorithmic or complexity point of view) has become useful in disciplines outside of the 'standard domain' of computer science. In ...
- 10.3k
11
votes
7
answers
3k
views
How does Theoretical Computer Science relate to security?
When I think of software that is insecure I think that it is "too useful" and can be abused by an attacker. So in a sense securing software is the process of making software less useful. In ...
- 528
262
votes
11
answers
101k
views
What is the enlightenment I'm supposed to attain after studying finite automata?
I've been revising Theory of Computation for fun and this question has been nagging me for a while (funny never thought of it when I learnt Automata Theory in my undergrad). So "why" exactly do we ...
- 5,355
71
votes
7
answers
4k
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 ...
- 27.6k
68
votes
7
answers
5k
views
Are $PSPACE$-complete problems inherently less tractable than $NP$-complete problems?
Currently, solving either a $NP$-complete problem or a $PSPACE$-complete problem is infeasible in the general case for large inputs. However, both are solvable in exponential time and polynomial space....
- 4,720
59
votes
6
answers
4k
views
Theoretical explanations for practical success of SAT solvers?
What theoretical explanations are there for the practical success of SAT solvers, and can someone give a "wikipedia-style" overview and explanation tying them all together?
By analogy, the smoothed ...
- 37.9k
39
votes
2
answers
3k
views
Mulmuley's GCT program
It is sometimes claimed that Ketan Mulmuley's Geometric Complexity Theory is the only plausible program for settling the open questions of complexity theory like P vs. NP question. There has been ...
- 4,041
31
votes
4
answers
5k
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 ...
- 427
10
votes
3
answers
623
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 ...
- 7,658
53
votes
4
answers
4k
views
Why do we consider log-space as a model of efficient computation (instead of polylog-space) ?
This might be a subjective question rather than one with a concrete answer, but anyway.
In complexity theory we study the notion of efficient computations. There are classes like $\mathsf{P}$ stands ...
- 7,658
45
votes
4
answers
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 ...
- 655
32
votes
11
answers
2k
views
What is the quantum computational model?
I have occasionally heard people talk about quantum algorithms and about states and the ability to consider multiple possibilities at once, but I have never managed to get someone to explain the ...
- 475
28
votes
2
answers
2k
views
Why is there an enormous difference between SAT solvers?
SAT solvers are very important in algebraic attacks, for example walksat and minisat.
However, when solving the benchmark problems available here there is an enormous performance difference between ...
- 383
27
votes
5
answers
2k
views
Ecology and evolution through the algorithmic lens
The study of ecology and evolution is becoming increasingly more mathematical, but most of the theoretical tools seem to be coming from physics. However, in many cases the problems have a very ...
- 10.3k
22
votes
3
answers
1k
views
Limits to Parallel Computing
I am curious in a broad sense about what is known about parallelizing algorithms in P. I found the following wikipedia article about the subject:
http://en.wikipedia.org/wiki/NC_%28complexity%29
The ...
- 221
14
votes
2
answers
849
views
Landscape of interactive proof systems
My first question is whether an interactive proof system characterisation is known for all the classic complexity classes. I would call P, NP, PSPACE, EXP, NEXP,EXPSPACE, recursive and recursively ...
- 12.6k
329
votes
29
answers
203k
views
Core algorithms deployed
To demonstrate the importance of algorithms (e.g. to students and professors who don't do theory or are even from entirely different fields) it is sometimes useful to have ready at hand a list of ...
- 7,689
95
votes
7
answers
30k
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/...
- 5,355
77
votes
4
answers
43k
views
Why is 2SAT in P?
I've come across the polynomial algorithm that solves 2SAT. I've found it boggling that 2SAT is in P where all (or many others) of the SAT instances are NP-Complete. What makes this problem different? ...
- 1,225
71
votes
5
answers
6k
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 ...
- 1,983
64
votes
5
answers
5k
views
Overarching reasons why problems are in P or BPP
Recently, when talking to a physicist, I claimed that in my experience, when a problem that naively seems like it should take exponential time turns out nontrivially to be in P or BPP, an "overarching ...
- 13.8k
56
votes
3
answers
3k
views
Surprising algorithms for counting problems
There are some counting problems which involve counting exponentially many things (relative to the size of the input), and yet have surprising polynomial-time exact, deterministic algorithms. Examples ...
- 2,013
47
votes
5
answers
1k
views
Are there Conservation Laws in Complexity Theory?
Let me start with some examples. Why is it so trivial to show CVP is in P but so hard to show LP is in P; while both are P-complete problems.
Or take primality. It is easier to show composites in NP ...
- 3,883
29
votes
6
answers
2k
views
Why naturals instead of integers?
I'm interested in why natural numbers are so beloved by the authors of books on programming languages theory and type theory (e.g. J. Mitchell, Foundations for programming languages and B. Pierce, ...
- 1,103
25
votes
4
answers
4k
views
Arguments for existence of one-way functions
I have read in several papers that the existence of one-way functions is widely believed. Can someone shed light on why this is the case? What arguments do we have for supporting the existence of one-...
- 4,041
18
votes
11
answers
5k
views
Are there any applications of techniques in real analysis to theoretical computer science?
I have looked far and wide for such applications and have mostly turned up short. I can find plenty of applications of topology and similar structures on countable (or uncountable) sets, but rarely do ...
17
votes
1
answer
1k
views
Career in Theoretical Computer Science
I am currently a high school student, interested in theoretical computer science and applied mathematics. I have self taught myself linear algebra and calculus and concrete mathematics. I have a naive ...
- 171
16
votes
10
answers
3k
views
Intractability of NP-complete problems as a principle of physics?
I'm always intrigued by the lack of numerical evidence from experimental mathematics for or against the P vs NP question. While the Riemann Hypothesis has some supporting evidence from numerical ...
- 21.1k
14
votes
2
answers
2k
views
What is theoretical computer science?
What exactly is theoretical computer science? Is it learning to code in various language and making apps in platforms? Or is it just thinking about faster and faster algorithms so that you can achieve ...
- 157
11
votes
2
answers
694
views
Best alien communication protocol?
Let's say we discover alien civilizations that are able to send and receive messages using an interstellar digital communications channel. (Say using modulated radio waves, laser pulses, re-...
- 295
10
votes
2
answers
831
views
Understanding QMA
This question comes out of an answer Joe Fitzsimons gave to a different question. Most natural complexity classes have a one-line "intuitive description" that helps characterize core problems in that ...
- 32.2k
10
votes
3
answers
738
views
Why don't we use larger classes to study determinism vs non-determinism?
In a previous question about time hierarchy, I've learned that equalities between two classes can be propagated to more complex classes and inequalities can be propagated to less complex classes, with ...
- 3,806
9
votes
1
answer
479
views
Does There exist a particular PSPACE Complete Problem which has a FPTAS algorithm?
It is well known that the NP-Complete Problem called Subset Sum has a FPTAS. I was wondering if there existed an PSPACE Complete problem which also has a FPTAS? Thanks in advance.
- 1,598
9
votes
1
answer
340
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{...
- 13.2k
7
votes
0
answers
374
views
Examples of non-CSLs not created through diagonalization
Hopcroft & Ullman 1979, Intro to Automata Theory, Languages, & Computation states (p. 224) that "almost any language one can think of is CSL; the only known proofs that certain languages are ...
- 11.1k
2
votes
1
answer
264
views
DFSA and NFSA intersection problem
Given $k$ deterministic FSAs of $n$ states the intersection of their languages is empty is decidable in $n^{o(k)}$ time is an open problem.
For unbounded $k$ it is known the problem is $PSPACE$ ...
- 13.2k
0
votes
0
answers
225
views
$CH=UL$ and partial breaking of transitive closure bottleneck problem and Savitch's theorem?
Let $L^t=DSPACE[O(\log n)^t]$, $NL^t=NSPACE[O(\log n)^t]$ and $UL^t=USPACE[O(\log n)^t$.
Savitch provides $NL\subseteq L^{2}$.
If $CH=UL$ we clearly got rid of the transitive closure bottleneck ...
- 13.2k