Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Top Questions

0 votes
2 answers
19 views

How can software developers ensure the security of their softwares, so that consumers don't mess with it?

1 vote
1 answer
18 views

Basic questions regarding a computer

0 votes
1 answer
35 views

Two Generals' Problem - Thought Experiment

6 votes
14 answers
6k views

Why is the Turing machine considered effective computation if it's not realizable due to the Bekenstein bound?

1 vote
1 answer
32 views

Why we can reduce $A_{TM}$ to $ALL_{CFG}$, but we can not reduce $A_{TM}$ to $E_{CFG}$

0 votes
2 answers
63 views

Why is my O(n^2 * 2^n) code faster than O(n * 2^n) and O(2^n) codes for the LeetCode "Beautiful Subsets" problem?

0 votes
1 answer
41 views

Why Does Computable Analysis Use Type 2 Turing Machines Over Type 1 TM's?

2 votes
1 answer
31 views

Does NSPACE($n^2$) $=$ DSPACE($n^4$)?

1 vote
1 answer
24 views

Finding a matching with a specific weight

0 votes
0 answers
14 views

Analysis of LRU algorithm with uniformly random access

0 votes
0 answers
30 views

RAM architecture vs. CPU architecture

1 vote
1 answer
479 views

Definition feels contradictory (Computational Complexity Theory)

2 votes
2 answers
37 views

Least interrupted max flow after removing K edges algorithm

1 vote
1 answer
44 views

Using XOR operation, a MOD operation compute a function f(n)

0 votes
0 answers
11 views

Dot Find Function in Python [closed]

0 votes
1 answer
70 views

problem understanding proof about deterministic pushdown automaton

0 votes
1 answer
44 views

Is the language L = {a^m b^n a^n b^m | m, n >= 1} context free?

2 votes
0 answers
25 views

Harder version of the k-partition problem

13 votes
3 answers
3k views

Why are search problems assumed to have the structure of "find a path in a graph"?

0 votes
1 answer
27 views

Using reducibility to prove a language that accepts $\lambda$ and either loops or accepts other strings is undecidable

-2 votes
0 answers
23 views

Design DFA to accept language a* + ab

0 votes
0 answers
14 views

Derivation for BNF

0 votes
2 answers
67 views

How much do llms know?

1 vote
0 answers
13 views

Is it known whether EXP is contained/not-contained in P/log?

-2 votes
0 answers
22 views

Theory of automata [closed]

1 vote
1 answer
379 views

If coNP ⊆ NP, does that mean coNP = NP?

0 votes
2 answers
46 views

Help regarding a proof in which i am able to prove a regular language $(a(a+b)*)$ as irregular using pumping lemma

0 votes
1 answer
19 views

How to count primitive Operations

0 votes
6 answers
59 views

Efficient data structure for multidimensional lookup

0 votes
0 answers
31 views

Confusion on 1 bit precession

3 votes
1 answer
52 views

Is there an algorithm for rearranging a set in a specific way while optimizing for minimum amount of moves?

1 vote
0 answers
74 views

Constructing simple polygon from non-crossing orthogonal line segments

0 votes
0 answers
19 views

Is memory barrier NECESSARY for memory consistency?

4 votes
1 answer
27 views

Why Normalisation by Evaluation needs to use a different representation of programs?

0 votes
1 answer
38 views

Binary subset rank and unrank

-1 votes
0 answers
16 views

Calculate the throughput of a channel using Go-Back-N protocol with given communication parameters

4 votes
2 answers
1k views

Global optimization of state assignments in a directed graph with a tree-based distance cost

0 votes
0 answers
13 views

Incorrect integration results in Adaptive Quadrature routine with periodic functions

0 votes
1 answer
12 views

Constraints on the order of program semantics given by an enumeration of turing-complete system programs

0 votes
4 answers
88 views

Proof that the mind/brain is not a finite state machine by recognizing an unrecognizable language?

0 votes
1 answer
17 views

Generating all unique (tape content, head position) possibilities for a Turing Machine

3 votes
1 answer
73 views

Maximum network flow with few non-integral edges

1 vote
1 answer
182 views

How to solve a system of XOR equations in a cyclic graph?

2 votes
1 answer
26 views

Number of configurations, non-deterministic $LBA$ and $A_{LBA}$

0 votes
0 answers
139 views

Turing Machine transition table for checking a palindrome

0 votes
1 answer
34 views

Balancing tree by removing nodes instead of perfoming rotations to defined height $h$

0 votes
1 answer
17 views

Concise definitions for different types of computational problems


Looking for more? Browse the complete list of questions, or popular tags. Help us answer unanswered questions.