Skip to main content

Top Questions

3 votes
0 answers
11 views

Is it decidable if $\text{MIN}(L(G))$ and $\text{MAX}(L(G))$ is context-free for a context-free grammar $G$?

0 votes
1 answer
158 views

PageRank vector

1 vote
1 answer
6 views

linear relationship between the log-odds and the features

0 votes
1 answer
18 views

Suppose we have two variables $x,y \in [1,n]$. How can we write $x \neq y$ in linear constraint?

0 votes
1 answer
148 views

Restriction of SAT to CNF

0 votes
1 answer
24 views

Optimizing Set Composition with String Edit Distance Constraints

0 votes
0 answers
15 views

Is complement of this language context-free? [duplicate]

1 vote
1 answer
10 views

Intuitive explanation/overview of non-looping non-termination proofs

0 votes
1 answer
25 views

A decision procedure for PCP

28 votes
8 answers
80k views

Why can't DFS be used to find shortest paths in unweighted graphs?

0 votes
0 answers
3 views

Counting Towers Recurrence Verification From CSES Problem Set

1 vote
0 answers
34 views

Compiler that compiles to a Universal Turing Machine (UTM)?

2 votes
2 answers
78 views

pumping lemma, concatenation of non-regular languages $a \neq b$

-1 votes
0 answers
28 views

is K-SAT equivalent to comparing between 2 intervals problem?

0 votes
0 answers
10 views

$L \ regular \to L'=\left \{ xy^{R}z : xyz\in L\ , x,y,z\in\Sigma^{*} \right \} \ regular$ [duplicate]

4 votes
2 answers
12k views

Finite state automata, multiple completion states?

0 votes
1 answer
203 views

Algorithm to distribute group of connected nodes in a graph

-1 votes
1 answer
28 views

is my attempt correct? proof that L in P or in NPC? $L=\{G$ is an undirected graph on n vertices VC $U$ and an IS $I$ such that $|U|+|I|=n+10$ \}

-2 votes
1 answer
18 views

Color conversions formulas

0 votes
2 answers
210 views

How to prove Big-O when $f(n)$ is defined sectionwise

1 vote
2 answers
33 views

What is the Computational Complexity of this Difference of Squares problem?

1 vote
2 answers
104 views

Prove that a language does not many one reduce to its complement

5 votes
2 answers
4k views

Is the Rice Theorem applicable for these problems?

0 votes
1 answer
138 views

CFG for the given language $L = \{~ a^\ell a^n b^m c^m d^n e^\ell ~|~ \ell,n,m \geq 0 \}$

0 votes
1 answer
24 views

Does a processing architecture exist that parallelises division operations?

0 votes
1 answer
36 views

can programming language be described by ambiguous grammar, if yes, will that cause any problem?

11 votes
2 answers
3k views

Is Desmos Turing-Complete?

0 votes
1 answer
35 views

Question about data to train an machine learning IA

-1 votes
0 answers
29 views

Showing that $SAT-2 \in P$ [duplicate]

0 votes
0 answers
18 views

How can i allocate troops so as to maximize the number of bases conquered without going over a maximum time?

0 votes
2 answers
38 views

Lossless compression collision such as 2 different files gives the same zip file after compression

0 votes
0 answers
16 views

Final outputs of running multiple processes at the same time

0 votes
2 answers
184 views

Create binary numbers with a described pattern

2 votes
2 answers
62 views

Max cut 2-approximation algorithm

0 votes
1 answer
27 views

Is this formulation for a turing machine proper?

0 votes
2 answers
31 views

Recursive grid search of a sorted matrix

8 votes
2 answers
4k views

Linearizability and Serializability in context of Software Transactional Memory

0 votes
1 answer
79 views

Need help with recurrence relation and postcondition of a function

1 vote
1 answer
195 views

Somewhat-hardware-conscious algorithm for top k-of-n with $k=\Omega(\sqrt{n})$

1 vote
4 answers
114 views

The Hydra Game algorithm

0 votes
0 answers
20 views

Knuth–Morris–Pratt algorithm - Determine the next position of the proper prefix of the pattern string

0 votes
1 answer
33 views

In what sense do universes solve the problem of not having type $\Pi_{A:\text{Type}}B(A)$?

10 votes
1 answer
460 views

Shift-resolve parsing - questions

0 votes
1 answer
151 views

Find the total no. of strings ( len n ) possible given a set of sets of letters such that no two letter from a single set should be in that string

0 votes
1 answer
526 views

Counting chords intersections in a circle

0 votes
2 answers
22 views

TOPS trillion operations per second to Tokens per second

1 vote
1 answer
113 views

Generalization of a Markov random field and a Bayesian network?

0 votes
0 answers
25 views

Algorithm of min copies needed to make up a string


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