We’re rewarding the question askers & reputations are being recalculated! Read more.

Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.

Sign up to join this community

Anybody can ask a question

Anybody can answer

The best answers are voted up and rise to the top

Explore our Questions

more tags

Active 1 Bountied Hot Week Month

2

votes

0

answers

132

views

How do computers check if two functions are the same?

lo.logic functional-programming proof-assistants

asked Nov 11 at 13:18 Student 129

10

votes

0

answers

291

views

Is unary $\Pi_2$-SUBSETSUM coNP-complete?

cc.complexity-theory np-hardness complexity-classes lo.logic

modified Oct 31 at 13:14 Alexey Milovanov 1,457

17

votes

2

answers

1k

views

Smallest possible universal combinator

lo.logic computability lambda-calculus universal-computation combinatory-logic

modified Oct 20 at 23:24 user76284 378

0

votes

0

answers

90

views

Fagin's Theorem implications

lo.logic np

asked Oct 13 at 13:49 gifa 21

1

vote

0

answers

77

views

Cover set of Boolean formulas with conjunctions

lo.logic boolean-functions boolean-formulas covering-problems

asked Oct 10 at 1:11 madbeebop 19

10

votes

0

answers

171

views

On Courcelle's question about Monadic second-order logic with cardinality predicates

cc.complexity-theory complexity-classes lo.logic polynomial-time

asked Oct 9 at 9:38 Alexey Milovanov 1,457

5

votes

0

answers

75

views

Are there languages require many variables to achieve $\Sigma_n^0$ completeness?

lo.logic computability

modified Sep 17 at 18:35 Stella Biderman 986

0

votes

0

answers

74

views

Transforming Lambda Calculus syntax into generic relations between finite strings

lo.logic lambda-calculus

modified Sep 16 at 15:56 polcott 11

18

votes

1

answer

3k

views

Prove proof irrelevance in Coq?

lo.logic type-theory proof-assistants coq

modified Aug 26 at 15:40 arvixx 103

5

votes

2

answers

436

views

Good description of Calculus of Inductive Construction

lo.logic dependent-type

modified Aug 26 at 8:40 Steven Shaw 474

0

votes

0

answers

130

views

Proofs for Implementation Statements

lo.logic se.software-engineering

modified Aug 26 at 6:49 Thomas Klimpel 2,798

14

votes

0

answers

164

views

Counting solutions to extended MSO formulas, and sampling — do these appear in the literature?

cc.complexity-theory lo.logic treewidth

modified Jul 29 at 13:30 Lorenzo Najt 1,087

2

votes

0

answers

86

views

Forward chaining algorithms

lo.logic

asked Jul 11 at 19:17 Enrique Pérez Arnaud 21

7

votes

0

answers

235

views

Reverse Skolemization?

reference-request lo.logic sat boolean-functions first-order-logic

modified Jul 7 at 22:28 jmite 2,120

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled