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
10
votes
3answers
674 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 ...
45
votes
7answers
6k 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 ...
18
votes
5answers
1k views

Why is it important to prove that a problem is NP-complete?

Am I correct in understanding that proving a problem NP complete is a research success? If so why?
48
votes
4answers
3k 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 ...
11
votes
4answers
627 views

Human intelligence and algorithms

Have there been any studies to determine whether human intelligence can outperform algorithms (i.e. test whether the No Free Lunch Theorem applies to human intelligence)? Along the same lines, has ...
22
votes
1answer
473 views

Energy considerations on computation

In order to check my understanding, I would like to share some thoughts about energy requirements of computation. This is a follow up to my previous question and might be related to Vinay's question ...
9
votes
1answer
361 views

Is there a relationship between computational complexity theory and complex systems theory?

Computational complexity theory classifies problems according to their inherent difficulty. Complex systems theory addresses systems that exhibit behaviours that do not obviously arise from the ...
9
votes
2answers
375 views

The complexity of Area-lawed Hamiltonians

I have recently thought about "importing" some physics-related question into quantum CS: The notion of the area-law phenomenon in Hamiltonian systems usually stands for a local Hamiltonian on some ...
46
votes
5answers
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 ...
18
votes
4answers
913 views

Applications of Complexity Theory

Complexity theory seems to capture something fundamental about the structure of the universe, in that it formalizes the intuitive notion that some problems are harder than others. Scott Aaronson ...
39
votes
3answers
2k views

Why are mod_m gates interesting?

Ryan Williams just posted his lower bound on ACC, the class of problems that have constant depth circuits with unbounded fan-in and gates AND, OR, NOT and MOD_m for all possible m's. What's so ...
9
votes
1answer
405 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.
43
votes
5answers
6k 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 ...
17
votes
3answers
682 views

Randomize or Not?

This question is inspired by the Georgia Tech Algorithms and Randomness Center's t-shirt, which asks "Randomize or not?!" There are many examples where randomizing helps, especially when operating in ...
21
votes
3answers
779 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 ...
66
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 ...
8
votes
2answers
450 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 ...
15
votes
10answers
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 ...
34
votes
2answers
2k 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 ...
24
votes
3answers
863 views

Can we quantify the “degree of quantumness” in a quantum algorithm ?

Entanglement is often held up as the key ingredient that makes quantum algorithms well... quantum, and this can be traced back to the Bell states that destroy the idea of quantum physics as a hidden-...
19
votes
4answers
2k views

How are side effects handled in semantics?

In Anthony Aaby's "Introduction to Programming Languages" section on Semantics, he makes the following observation: Much of the work in the semantics of programming languages is motivated by ...
32
votes
11answers
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 ...
11
votes
7answers
2k 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 ...
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 ...