Problem Detail: I have no idea how I managed to get this far in life without ever really grasping this but as it happens I’m still very confused on the concept of a hash function. I did some googling/wikipedia-ing, and here’s Read More …
Category: Uncategorized
[Solved]: How to prove formally that grammar isn’t LR(1)
Problem Detail: I want to prove that grammar $$ begin{cases} S’rightarrow S Srightarrow aSb ~|~ A Arightarrow bA~|~b end{cases} $$ isn’t $LR(1)$. I’ve constructed parser table and got Shift-Reduce conflict. I want to prove that without parser table, using another $LR(1)$ Read More …
[Solved]: Undecidability of a restricted version of the acceptance problem
Problem Detail: It’s known that the following language, the so-called acceptance problem is undecidable: $A_{TM} = {langle M,wrangle,vert,Mtext{ is a TM which accepts }w}$ The proof is by contradiction: Assume there is a TM $H$ which decides $A_{TM}$. Let $D$ be Read More …
[Solved]: Algorithm for computing volume of union or intersection of n-dimensional convex polytopes given their facets?
Problem Detail: I’ve googled this problem somewhat pretty extensively, and all the relevant literature understandably deals with 2-d or 3-d cases, rather than the n-d case. EDIT: Yes, ℝn. I’ve done many searches combining terms like union, intersection, volume, convex hulls, Read More …
[Solved]: Can we check in polynomial time if the language of a DFA is closed against Kleene star?
Problem Detail: I was wondering if there is a polynomial time algorithm to test whether a DFA recognizes a star closed language ( which is if $A=A^*$). I think that yes, but I do not have an idea to do it. Read More …
[Solved]: Order a list of whole numbers so that no two numbers have the average of them sitting between them
Problem Detail: Given a whole number N.. Arrange 1 to N in a sequence such that no two numbers have their average sitting between them… Note – If N=20.. average of 19 and 2 = 10.5 is not a whole number Read More …
[Solved]: Proof that ${⟨M⟩ ∣ L(M) mbox{ is context-free} }$ is not (co-)recursively enumerable
Problem Detail: I would like to use your help with the following problem: $L={⟨M⟩ ∣ L(M) mbox{ is context-free} }$. Show that $L notin RE cup CoRE$. I know that to prove $Lnotin RE$, it is enough to find a language Read More …
[Solved]: Is the language of TMs that decide some language Turing-recognizable?
Problem Detail: Is the language $qquad L={ langle text{M} rangle ; | ; text{M is a Turing machine that decides some language} }$ a Turing-recognizable language? I think it’s not, as, even if I am able to tell somehow that a Read More …
[Solved]: Pseudo polynominal time algorithm for Np-Complete Problems
Problem Detail: For problems like knapsack there is pseudopolynominaltime algorithm and it is np-complete. So we reduce every other problem in np in polytime to knapsack. But why don’t we have then a pseudopolynominaltime algorithm for all problems in np? Asked Read More …
[Solved]: Can a transcendental number like $e$ or $pi$ be compressed as not algorithmically random?
Problem Detail: The related and interesting fields of Information Theory, Turing Computability, Kolmogorov Complexity and Algorithmic Information Theory, give definitions of algorithmically random numbers. An algorithmically random number is a number (in some encoding, usually binary) for which the shortest program Read More …
