Questions tagged [proof-techniques]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
78
votes
5answers
4k views

Techniques for Reversing the Order of Quantifiers

It is well-known that in general, the order of universal and existential quantifiers cannot be reversed. In other words, for a general logical formula $\phi(\cdot,\cdot)$, $(\forall x)(\exists y) \...
56
votes
18answers
2k views

Where and how did computers help prove a theorem?

The purposes of this question is to collect examples from theoretical computer science where the systematic use of computers was helpful in building a conjecture that lead to a theorem, falsifying a ...
41
votes
9answers
5k views

References for TCS proof techniques

Are there any references (online or in book form) that organize and discuss TCS theorems by proof technique? Garey and Johnson do this for the various kinds of widget constructions needed for NP-...
8
votes
2answers
276 views

New Space Lower-Bound Techniques for Streaming Algorithms

Is communication complexity (CC) the only known approach for streaming algorithms lower bounds? Are there any other techniques, even if conditional lower bounds? In general, are we satisfied with the ...
1
vote
0answers
60 views

Some examples of tools to demonstrate problem is in $NC$ [closed]

Unlike the class $P$ or $NP$ the class $NC$ does not have any complete problems. To show a problem is in $NC$ one needs to marshal efforts to directly show the problem is in $NC$ since there are no ...
0
votes
1answer
110 views

Semantic equivalence using a model of computation of two languages

I am relatively new to the field of language semantics. However i had a question pertaining to language equivalence (i did read about the question, however my approach is slightly different and hence ...