Skip to main content

Questions tagged [proof-techniques]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers

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 ...
Turbo's user avatar
  • 13k
0 votes
1 answer

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 ...
anil keshav's user avatar
8 votes
2 answers

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 ...
user34384's user avatar
83 votes
5 answers

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) \...
Sadeq Dousti's user avatar
  • 16.5k
44 votes
9 answers

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-...
58 votes
18 answers

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 ...