Theoretical Computer Science Stack Exchange
Theoretical Computer Science Stack Exchange

Most Popular

more tags
1500 questions
30
votes
10 answers

Great algorithms, machine learning and no linear algebra

I teach an advanced algorithms course and would like to include some topics related to machine learning which will be of interest to my students. As a result, I would like to hear people's opinions of the currently most interesting/greatest…
Simd
  • 3,902
  • 20
  • 49
30
votes
2 answers

Polynomial method for complexity results

Polynomial methods, say Combinatorial Nullstellensatz and Chevalley–Warning theorem are powerful tools in additive combinatorics. By representing a problem with proper polynomials, they can guarantee the existence of a solution, or the number of…
Hsien-Chih Chang 張顯之
  • 7,638
  • 4
  • 44
  • 83
30
votes
2 answers

Are lambda calculus and combinatory logic the same?

I am currently reading "Lambda-Calculus and Combinators" by Hindley and Seldin. I'm not an expert, but have always taken an interest in lambda calculus because of involvement with functional programming (starting with Lisp and SICP, and now with R…
Shane
  • 2,233
  • 3
  • 26
  • 25
30
votes
7 answers

Lipton's most influential results

Richard J. Lipton has been selected as the winner of the 2014 Knuth Prize "for Introduction of New Ideas and Techniques". What are to your minds the main new ideas and techniques that Lipton developed? Note. This question shall become community…
Bruno
  • 4,449
  • 33
  • 45
30
votes
6 answers

Maximum computational power of a C implementation

If we go by the book (or any other version of the language specification if you prefer), how much computational power can a C implementation have? Note that “C implementation” has a technical meaning: it is a particular instantiation of the C…
Gilles 'SO- stop being evil'
  • 2,667
  • 1
  • 27
  • 35
30
votes
1 answer

Are there canonical non-relativizing techniques?

In a lot of domains, there are canonical techniques which everybody working in the field should master. For example, for logspace reductions, the "bit trick" for composition consisting of not constructing the full output of the composed function,…
Ludovic Patey
  • 1,763
  • 11
  • 22
30
votes
3 answers

A decision problem which is not known to be in PH but will be in P if P=NP

Edit: As Ravi Boppana correctly pointed out in his answer and Scott Aaronson also added another example in his answer, the answer to this question turned out to be “yes” in a way which I had not expected at all. First I thought that they did not…
Tsuyoshi Ito
  • 16,466
  • 2
  • 55
  • 106
30
votes
3 answers

Translating SAT to HornSAT

Is it possible to translate a boolean formula B into an equivalent conjunction of Horn clauses? The Wikipedia article about HornSAT seems to imply that it is, but I have not been able to chase down any reference. Note that I do not mean "in…
Evgenij Thorstensen
  • 1,089
  • 10
  • 17
30
votes
2 answers

Is there a polynomial time algorithm to determine if the span of a set of matrices contains a permutation matrix?

I would like to find a polynomial time algorithm that determines if the span of a given set of matrices contains a permutation matrix. If any one knows if this problem is of a different complexity class, that would be just as helpful. EDIT: I've…
Nick
  • 483
  • 3
  • 6
30
votes
3 answers

Is there a candidate for a natural problem in $P/poly - P$?

I want to know if non-uniformity helps computing functions in practice. It is easy to show that there are functions in $P/poly - P$, take any uncomputable function $f$ and consider the language {$0^{f(n)}:n\in \omega$}, which clearly has simple…
Kaveh
  • 21,577
  • 8
  • 82
  • 183
30
votes
4 answers

Why do we need formal semantics for predicate logic?

Consider this question solved. I will not pick a best answer as all of them have contributed to my understanding of the topic. Im unsure what benefit we have by formally defining the semantics of predicate logic. But I do see value in having a…
Martin
  • 309
  • 3
  • 5
30
votes
7 answers

Why is CNF used for SAT and not DNF?

I don't quite understand why almost all SAT solvers use CNF instead of DNF. It seems to me that solving SAT is easier using DNF. After all, you just have to scan through the set of implicants and check whether one of them contains not both a…
Martin
30
votes
2 answers

Commonest Subsequence

A string has $2^n$ subsequences, but they are usually not all distinct. What is the complexity of finding the maximum frequency of any subsequence? For example, the string "subsequence" contains 7 copies of the subsequence "sue" and this is the…
daveagp
  • 1,100
  • 7
  • 14
30
votes
4 answers

Are there "small" machines which can efficiently match regular expressions?

It's well-known that a regular expression can be recognized by a nondeterministic finite automaton of size proportional to the regular expression, or by a deterministic FA which is potentially exponentially larger. Furthermore, given a string $s$…
Neel Krishnaswami
  • 32,528
  • 1
  • 100
  • 165
30
votes
1 answer

Halting problem, uncomputable sets: common mathematical proof?

It is known that with a countable set of algorithms (characterised by a Gödel number), we cannot compute (build a binary algorithm which checks belonging) all subsets of N. A proof could be summarized as: if we could, then the set of all subsets of…
Weier
  • 413
  • 4
  • 6
1 2 3
…
99 100