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 Hot Week Month

-3

votes

0

answers

75

views

Converting special cases of binary to unary in poly-time or is it pseudo-poly-time?

cc.complexity-theory unary-languages

modified 2 hours ago Travis Wells 1

6

votes

2

answers

395

views

Applications of Takens' theorem to TCS?

machine-learning lg.learning physics

answered 4 hours ago Kalinda Vathupola 1

0

votes

0

answers

16

views

Counting avoiding improper 3-colorings

reference-request counting-complexity

asked 9 hours ago M.Monet 471

-3

votes

0

answers

31

views

Convex minimization with linear constraints?

cc.complexity-theory optimization convex-optimization fixed-parameter-tractable semidefinite-programming

modified 17 hours ago Turbo 5,213

-1

votes

0

answers

40

views

Sparsity related to linear programming in $NC$?

cc.complexity-theory big-picture linear-programming dc.parallel-comp sparse-matrix

asked yesterday Turbo 5,213

1

vote

0

answers

59

views

How to prove a general convex set is nonempty or empty in polynomial time?

cc.complexity-theory time-complexity polynomial-time

modified yesterday IronMan 6

0

votes

0

answers

54

views

Shortest s-t Path with a covering constraint

graph-algorithms co.combinatorics network-modeling

modified yesterday Gamow 4,237

2

votes

1

answer

139

views

About a pre-processing step for primal–dual weighted set cover problem

approximation-algorithms set-cover

modified 2 days ago Community♦ 1

8

votes

1

answer

244

views

Winning strategy in the game of triplets

gt.game-theory combinatorial-game-theory

modified 2 days ago Yonatan N 1,301

3

votes

1

answer

86

views

Complexity of #PP2DNF where we also count on the number of clauses

cc.complexity-theory counting-complexity

answered 2 days ago a3nm 3,684

2

votes

1

answer

93

views

Consequences/existence of problems without any “optimal” algorithm

ds.algorithms complexity-classes time-complexity

answered Aug 21 at 3:43 Will Angley 146

-1

votes

0

answers

34

views

Functions Associative with Respect to Application

computability pl.programming-languages lambda-calculus functional-programming

asked Aug 20 at 22:45 rusini 1

6

votes

1

answer

151

views

3-coloring planar graphs in $O\left(3^{n^.5}\right)$?

cc.complexity-theory graph-algorithms planar-graphs graph-colouring

answered Aug 20 at 20:46 Alex Golovnev 1,438

0

votes

2

answers

345

views

Formalizing and optimizing constraints involving booleans, pairs of booleans, and integer sums

ds.algorithms optimization

answered Aug 19 at 23:25 Peter Taylor 1,225

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled