Theoretical Computer Science Stack Exchange

1 vote

1 answer

19 views

What are some practical applications of inductive-inductive and inductive-recursive types?

winitzki

327

answered 2 hours ago

0 votes

0 answers

16 views

Is there any augmenting graph algorithm available for find maximum independent set problem in K1,4 free graph

user72110

17

asked 8 hours ago

0 votes

0 answers

24 views

Reductions That Acts on Witnesses

Boran Erol

1

asked 10 hours ago

-2 votes

0 answers

36 views

Can any suggest good algorithmic problem on automata theory

Astrid Louvery

1

asked 18 hours ago

0 votes

0 answers

9 views

How well can shortest common supersequence over small alphabet size be approximated?

Hao S

198

modified 20 hours ago

13 votes

1 answer

617 views

Recent progress on the next-to-shortest-path problem for directed graphs?

CommunityBot

1

modified 23 hours ago

5 votes

0 answers

71 views

How to prove clock equivalence is a time-abstracted bisimulation

generic_logician

51

modified yesterday

0 votes

1 answer

70 views

Detecting Erroneous Corrections

CommunityBot

1

modified yesterday

-1 votes

0 answers

69 views

Are there any problems that take Sub-Exponential time outside of PSPACE?

Colonizor48

343

asked yesterday

8 votes

1 answer

219 views

Is any function between $n$ and $n\log n$ time-constructible on a 1-tape TM?

Neal Young

10.3k

modified yesterday

7 votes

2 answers

292 views

Proving #P-hardness for the number of subsets of a set of positive integers with a sum of at most T?

badboul

45

modified 2 days ago

1 vote

1 answer

162 views

Is (Restricted) Bigraph Isomorphism Weaker than Graph Isomorphism?

Oscar Bender-Stone

11

modified 2 days ago

0 votes

0 answers

38 views

Algorithm to remove unnecessary productions from context-free grammar

Cubozoa13

1

asked 2 days ago

0 votes

1 answer

70 views

Polynomial time algorihtms for two variants of the decision version of longest walk problem

NaturalLogZ

329

answered Mar 18 at 16:35

Stack Exchange Network

Explore our questions

What are some practical applications of inductive-inductive and inductive-recursive types?

Is there any augmenting graph algorithm available for find maximum independent set problem in K1,4 free graph

Reductions That Acts on Witnesses

Can any suggest good algorithmic problem on automata theory

How well can shortest common supersequence over small alphabet size be approximated?

Recent progress on the next-to-shortest-path problem for directed graphs?

How to prove clock equivalence is a time-abstracted bisimulation

Detecting Erroneous Corrections

Are there any problems that take Sub-Exponential time outside of PSPACE?

Is any function between $n$ and $n\log n$ time-constructible on a 1-tape TM?

Proving #P-hardness for the number of subsets of a set of positive integers with a sum of at most T?

Is (Restricted) Bigraph Isomorphism Weaker than Graph Isomorphism?

Algorithm to remove unnecessary productions from context-free grammar

Polynomial time algorihtms for two variants of the decision version of longest walk problem

Hot Network Questions