Theoretical Computer Science Stack Exchange
Theoretical Computer Science Stack Exchange

Most Popular

more tags
1500 questions
15
votes
1 answer

Natural theorems proven only "to high probability"?

There are plenty of situations where a randomized "proof" is much easier than a deterministic proof, the canonical example being polynomial identity testing. Question: Are there any natural mathematical "theorems" where a randomized proof is known…
Geoffrey Irving
  • 3,253
  • 15
  • 29
15
votes
3 answers

Does every greedy algorithm have matroid structure?

It is well established that for every matroid $M$ and any weight function $w$, there exits an algorithm $\mbox{GreedyBasis}(M,w)$ which returns a maximum weight basis of $M$. So, is the reverse direction also true? That is, if there is some greedy…
user3373748
15
votes
2 answers

Is every recursive language recognized by a mortal Turing machine?

We say that a Turing Machine $M$ is mortal if $M$ halts for every starting configuration (in particular, the tape content and initial state can be arbitrary). Is every recursive language recognized by a mortal Turing Machine? (i.e. if there is a TM…
Marcin Kotowski
  • 2,806
  • 19
  • 25
15
votes
1 answer

Are there "NP-Intermediate-Complete" problems?

Assume P $\ne$ NP. Ladner's Theorem says that there are NP Intermediate problems (problems in NP that are neither in P nor NP-Complete). I have found some veiled references online that suggest (I think) that there are many "levels" of mutually…
GMB
  • 2,393
  • 15
  • 20
15
votes
2 answers

GI-hard graph problem not known to be $NP$-complete

Graph Isomorphism ($GI$) is good candidate for $NP$-intermediate problem. $NP$-intermediate problems exist unless $P=NP$. I'm looking for natural problem that is hard for $GI$ under Karp reduction (A graph problem $X$ such that $GI <_p^m X$). Is…
Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149
15
votes
2 answers

Random 3-SAT: What is the consensus experimental range of the threshold?

The critical ratio of clauses to variables for random 3-SAT is more than 3 and less than 6, and seems to be commonly described as "around 4.2" or "around 4.25". Mezard, Parisi, and Zecchina prove (in the physics sense) that the critical ratio is…
Andrew D. King
  • 1,573
  • 10
  • 19
15
votes
2 answers

Why is lambda calculus a "calculus"?

The only definition of "calculus" I'm aware of is the study of limits, derivatives, integrals, etc. in analysis. In what sense is lambda calculus (or things like mu calculus) a "calculus"? How does it relate to calculus in analysis?
alecbz
  • 269
  • 1
  • 8
15
votes
2 answers

Approximation in subexponental time

There are studies about approximation algorithms for NP complete problems in Polynomial time and exact algorithms in exponential time. Are there studies about approximation algorithms for NP complete problems in subexponential time of form…
Turbo
  • 12,812
  • 1
  • 19
  • 68
15
votes
0 answers

Williams' Method, Natural Proofs and Constructivity

I have some questions on the previous question which is written bellow. Natural Proof and Constructivity : The topic of the previous question Recently, Ryan Williams proved that Constructivity in Natural Proof is unavoidable to derive a separation…
atsu
  • 171
  • 3
15
votes
0 answers

Are there other proofs for Barrington's theorem?

I know that you can use other non-solvable groups, but is there a proof that uses a completely different approach? In case someone would not know the theorem: http://en.wikipedia.org/wiki/NC_(complexity)#Barrington.27s_theorem
domotorp
  • 13,931
  • 37
  • 93
15
votes
6 answers

Geometric Interpretation of Computation

Being from Physics, I have been trained to look into a lot of problems from a geometrical point of view. For example the differential geometry of manifolds in dynamical systems etc. When I read the foundations of computer science, I always try to…
swarnim_narayan
  • 265
  • 1
  • 5
15
votes
3 answers

Complexity of topological sort with constrained positions

I am given as input a DAG $G$ of $n$ vertices where each vertex $x$ is additionally labeled with some $S(x) \subseteq \{1, \ldots, n\}$. A topological sort of $G$ is a bijection $f$ from the vertices of $G$ to $\{1, \ldots, n\}$ such that for all…
a3nm
  • 9,269
  • 27
  • 86
15
votes
6 answers

variations of SAT

I looked up on the internet, but I could not find any 'big-list' of variants of SAT problem. Apart from the (common) SAT, k-SAT, MAX-kSAT, Half-SAT, XOR-SAT, NAE-SAT what else variants are there? (also it will be really useful if there…
Subhayan
  • 831
  • 9
  • 19
15
votes
1 answer

Beigel-Tarui transformation of ACC cricuits

I am reading the appendix about ACC lower bounds for NEXP in Arora and Barak's Computational Complexity book. http://www.cs.princeton.edu/theory/uploads/Compbook/accnexp.pdf One of the key lemmas is a transformation from $ACC^{0}$ circuits to…
echuly
  • 549
  • 2
  • 8
15
votes
1 answer

How to define a function inductively on two arguments in Coq?

How can I convince Coq that the recursive function given below terminates? The function takes two inductive arguments. Intuitively, the recursion terminates because either argument is decomposed. Specifically, the function takes two trees as…
yhirai
  • 963
  • 7
  • 21
1 2 3
…
99 100