Theoretical Computer Science Stack Exchange
Theoretical Computer Science Stack Exchange

Most Popular

more tags
1500 questions
32
votes
3 answers

Consequences of existence of a strongly polynomial algorithm for linear programming?

One of the holy grails of algorithm design is finding a strongly polynomial algorithm for linear programming, i.e., an algorithm whose runtime is bounded by a polynomial in the number of variables and constraints and is independent of the size of…
Ian
  • 2,727
  • 20
  • 24
32
votes
2 answers

What's the difference between the Actor Model of Concurrency and Communicating Sequential Processes

I'm trying to wrap my head around what the real differences between the Actor Model of concurrency and Communicating Sequential Processes (CSP) model of concurrency. So far the best that I have been able to come up with is that the Actor Model…
twhitlock
  • 423
  • 4
  • 6
32
votes
1 answer

Is Gap-3SAT NP-complete even for 3CNF formulas where no pair of variables appears in significantly more clauses than the average?

In this question, a 3CNF formula means a CNF formula where each clause involves exactly three distinct variables. For a constant 0
Tsuyoshi Ito
  • 16,466
  • 2
  • 55
  • 106
32
votes
3 answers

Are any of the state of the art Maximum Flow algorithms practical?

For the maximum flow problem, there seem to be a number of very sophisticated algorithms, with at least one developed as recently as last year. Orlin's Max flows in O(mn) time or better gives an algorithm that runs in O(VE). On the other hand, the…
Rob Lachlan
  • 421
  • 4
  • 5
32
votes
7 answers

Should we consider $\mathsf{P} \neq \mathsf{NP}$ a law of nature?

Many experts believe that the $\mathsf{P} \neq \mathsf{NP}$ conjecture is true and use it in their results. My concern is that the complexity strongly depends on the $\mathsf{P} \neq \mathsf{NP}$ conjecture. So my question is: As long as the…
vb le
  • 4,828
  • 1
  • 37
  • 46
32
votes
15 answers

Complex analysis in theoretical computer science

There are many applications of real analysis in theoretical computer science, covering property testing, communication complexity, PAC learning, and many other fields of research. However, I can't think of any result in TCS that relies on complex…
user887
32
votes
0 answers

Combinatorics of Bellman-Ford or how to make cyclic graphs acyclic?

Roughly speaking, my question is: How costly is to make a cyclic graph acyclic while preserving all simple $s$-$t$ paths? Let $K_n$ be a complete undirected graph on vertices $\{0,1,\ldots,n+1\}$. (My apologies to purists: I should write…
Stasys
  • 6,765
  • 29
  • 54
32
votes
1 answer

Programming languages with canonical functions

Are there any (functional?) programming languages where all functions have a canonical form? That is, any two functions that return the same values for all set of input is represented in the same way, e.g. if f(x) returned x + 1, and g(x) returned x…
math4tots
  • 423
  • 3
  • 5
32
votes
1 answer

Eilenberg's rational hierarchy of nonrational automata & languages -- where is it now?

In the preface to his very influential books Automata, Languages and Machines (Volumes A, B), Samuel Eilenberg tantalizingly promised Volumes C and D dealing with "a hierarchy (called the rational hierarchy) of the nonrational phenomena... using…
David Lewis
  • 771
  • 5
  • 7
31
votes
6 answers

What is the difference between propositions and judgments?

I get confused by the subtle difference between propositions and judgments when exposed to intuitionistic type theory. Can any one explain to me what is the point to distinguish them and what distinguishes them? Especially in view of the…
day
  • 2,795
  • 1
  • 20
  • 27
31
votes
5 answers

Binary search generalizations for posets?

Suppose I have a poset "S" and a monotonic predicate "P" on S. I want to find one or all maximal elements of S satisfying P. EDIT: I'm interested in minimizing the number of evaluations of P. What algorithms do there exist for this problem and what…
jkff
  • 8,941
  • 3
  • 23
  • 33
31
votes
2 answers

What classes of mathematical programs can be solved exactly or approximately, in polynomial time?

I am rather confused by the continuous optimization literature and TCS literature about which types of (continuous) mathematical programs (MPs) can be solved efficiently, and which cannot. The continuous optimization community seems to claim that…
Bart
  • 516
  • 4
  • 6
31
votes
2 answers

Hierarchy for BPP vs derandomization

In one sentence: would the existence of a hierarchy for $\mathsf{BPTIME}$ imply any derandomization results? A related but vaguer question is: does the existence of a hierarchy for $\mathsf{BPTIME}$ imply any difficult lower bounds? Does the…
Sasho Nikolov
  • 18,189
  • 2
  • 67
  • 115
31
votes
3 answers

What is the difference between a second preimage attack and a collision attack?

Wikipedia defines a second preimage attack as: given a fixed message m1, find a different message m2 such that hash(m2) = hash(m1). Wikipedia defines a collision attack as: find two arbitrary different messages m1 and m2 such that hash(m1) =…
Thomas Owens
  • 413
  • 1
  • 4
  • 9
31
votes
3 answers

Justification of log f in DTIME hierarchy theorem

If we look at DTIME hierarchy theorem, we've got a log due to the overhead in simulation of a deterministic Turing Machine by a universal machine : $DTIME(\frac{f}{\log f}) \subsetneq DTIME(f)$ We haven't this kind of overhead for NTIME of DSPACE. A…
Ludovic Patey
  • 1,763
  • 11
  • 22
1 2 3
…
99 100