Computer Science Stack Exchange

0

votes

2

answers

42

views

Proof of the undecidability of compiler code optimization

undecidability compilers

modified 35 mins ago Dmitry 456

0

votes

1

answer

14

views

A monad is just a monoid in the category of endofunctors, what's the enlightenment?

functional-programming category-theory

answered 1 hour ago varkor 331

0

votes

0

answers

25

views

Scheduling jobs online on 3 identical machines - a lower bound of 5/3

algorithms scheduling online-algorithms competitive-ratio

modified 1 hour ago Felix 60

2

votes

2

answers

18

views

Intuition for Church-Turing thesis for Turing machines

turing-machines turing-completeness church-turing-thesis mu-recursion

modified 2 hours ago Aaron Rotenberg 2,929

0

votes

1

answer

27

views

Problem with proving that $RP \subseteq NP$ : a non-deterministic TM for a language $L \in RP$

complexity-theory reductions np complexity-classes randomness

modified 3 hours ago Community♦ 1

2

votes

2

answers

56

views

Is $EVEN-SAT$ $NP$-hard?

complexity-theory np-hard

answered 3 hours ago Lieuwe Vinkhuijzen 3,982

5

votes

1

answer

52

views

How to calculate the dimension of a convex polyhedron?

computational-geometry linear-programming

modified 3 hours ago Erel Segal-Halevi 5,066

0

votes

1

answer

40

views

Solving the Knapsack problem in $O(n^2P)$, where P is the maximum weight of all items

graphs dynamic-programming

modified 4 hours ago Community♦ 1

0

votes

2

answers

31

views

Does a regular expression exist for any number that contains no more than two 5s and no 6 twice in a row?

regular-languages finite-automata regular-expressions pumping-lemma

answered 4 hours ago vonbrand 11.8k

1

vote

0

answers

22

views

Number of words of length n for special language

formal-languages regular-languages combinatorics strings word-combinatorics

modified 5 hours ago Yuval Filmus 229k

0

votes

0

answers

10

views

Global-input-local-output p-time algorithms

algorithms satisfiability polynomial-time

asked 8 hours ago Zirui Wang 732

2

votes

1

answer

54

views

If $A$ is context-free then $A^*$ is regular

formal-languages regular-languages context-free

answered 8 hours ago Frank 61

2

votes

1

answer

20

views

Counting circuits with constraints

complexity-theory combinatorics circuits lower-bounds

answered 9 hours ago Yuval Filmus 229k

-1

votes

1

answer

38

views

Is English Turing-complete?

turing-machines turing-completeness

answered 13 hours ago Vor 11.7k

Jun	JUL	Aug
	22
2019	2020	2021

Stack Exchange Network

current community

your communities

more stack exchange communities

Explore our Questions

Proof of the undecidability of compiler code optimization

A monad is just a monoid in the category of endofunctors, what's the enlightenment?

Scheduling jobs online on 3 identical machines - a lower bound of 5/3

Intuition for Church-Turing thesis for Turing machines

Problem with proving that $RP \subseteq NP$ : a non-deterministic TM for a language $L \in RP$

Is $EVEN-SAT$ $NP$-hard?

How to calculate the dimension of a convex polyhedron?

Solving the Knapsack problem in $O(n^2P)$, where P is the maximum weight of all items

Does a regular expression exist for any number that contains no more than two 5s and no 6 twice in a row?

Number of words of length n for special language

Global-input-local-output p-time algorithms

If $A$ is context-free then $A^*$ is regular

Counting circuits with constraints

Is English Turing-complete?

Hot Network Questions