Theoretical Computer Science Stack Exchange

-1

votes

0

answers

6

views

Prove that if P = NP, then Σ2SAT is in P

complexity

asked 33 mins ago a 123 1

1

vote

0

answers

16

views

Does the Hindley-Milner type system (i.e. STLC with prenex polymorphism) have a category-theoretic model?

pl.programming-languages ct.category-theory type-systems type-inference

asked 9 hours ago xrq 975

0

votes

0

answers

39

views

Is the edge cover polytope integral on graphs with self-loops?

graph-theory linear-programming integer-programming polytope

modified 12 hours ago Karagounis Z 67

1

vote

2

answers

90

views

Complexity of Model Enumeration in function free, equality free, First Order Logic with only Unary Predicates?

counting-complexity first-order-logic

modified yesterday Emil Jeřábek 11.5k

6

votes

0

answers

66

views

Find min-weight simple path assuming no negative simple cycles

graph-algorithms

modified yesterday Craig Gidney 1,338

-1

votes

0

answers

44

views

Are all computable functions monoidal from a category theory POV?

computability ct.category-theory

modified yesterday PhD 4,887

4

votes

2

answers

125

views

Reducing the Height of Context-Free Grammars

reference-request context-free parsing

answered Jul 22 at 14:10 gsv 61

3

votes

0

answers

62

views

Dynamic matrix-matrix multiplication

matrices matrix-product dynamic-algorithms boolean-matrix

asked Jul 22 at 13:49 gsv 61

0

votes

0

answers

32

views

Comparing two graphs when starting from a single edge

graph-theory graph-algorithms graph-isomorphism

asked Jul 22 at 11:13 michael023411 1

0

votes

0

answers

33

views

Proving membership in W-hierarchy when problem is not parameterized by its solution size

parameterized-complexity fixed-parameter-tractable

modified Jul 22 at 6:30 Haden Hooyeon Lee 113

-2

votes

0

answers

29

views

What separates Set Disjointness from Equality in randomized complexity?

communication-complexity

asked Jul 22 at 6:09 Vane 1

3

votes

1

answer

79

views

Isomorphism preserving transformation CNF to Graph?

graph-theory sat graph-isomorphism

answered Jul 21 at 23:54 D.W. 9,143

0

votes

0

answers

13

views

Find a boundary from set of 3d line segments

graph-algorithms computational-geometry

asked Jul 21 at 22:08 Yakov 189

Jun	JUL	Aug
	25
2019	2020	2021

Stack Exchange Network

current community

your communities

more stack exchange communities

Explore our Questions

Prove that if P = NP, then Σ2SAT is in P

Does the Hindley-Milner type system (i.e. STLC with prenex polymorphism) have a category-theoretic model?

Is the edge cover polytope integral on graphs with self-loops?

Complexity of Model Enumeration in function free, equality free, First Order Logic with only Unary Predicates?

Find min-weight simple path assuming no negative simple cycles

Are all computable functions monoidal from a category theory POV?

Reducing the Height of Context-Free Grammars

Dynamic matrix-matrix multiplication

Comparing two graphs when starting from a single edge

Proving membership in W-hierarchy when problem is not parameterized by its solution size

What separates Set Disjointness from Equality in randomized complexity?

Isomorphism preserving transformation CNF to Graph?

Find a boundary from set of 3d line segments

Hot Network Questions