Problem Detail: I know that if one-way functions exist then there are certain universal one-way functions that exist, but to my knowledge they are too impractical to implement (which is the main reason why they are not being used in modern Read More …
Category: Uncategorized
[Solved]: Find all the paths from node A to node B
Problem Detail: You are given a bunch of nodes evenly spaced in a rectangular grid. The rectangle is M nodes long and N nodes wide. Node A is in the upper left hand (northwest) corner and node B is at the Read More …
[Solved]: Can there be two different left most derevations for a grammar?
Problem Detail: Suppose there is a CFG with the rules S–> Aa A–> Bb B–> A B–> Epsilon To my best understanding the left most derivation would go like this.. S==> Aa ==> Bba ==> Aba ==> Bbba ==> bba or Read More …
[Solved]: How to apply a 1-qubit gate to a single qubit from an entangled pair?
Problem Detail: Reading about superdense coding I came upon a calculation I can not understand. We have an EPR entangled pair of qubits $frac{1}{sqrt2}(|00rangle + |11rangle)$ and we want to apply a Pauli X gate to the first of the entangled Read More …
[Solved]: Language consisting of all Turing machine encodings
Problem Detail: $A=${$ ⟨M⟩$:$M$ $is$ $a$ $Turing$ $Machine$ } What can be said about $A$ ? Specifically, is $A$ decidable,regular,CFL,CSL? I would say $A$ is decidable since we can write an algorithm to check whether a string is a valid encoding Read More …
[Solved]: are there any decidable problems not verifiable in polynomial time?
Problem Detail: As I understand it NP requires a solution to be verifiable in polynomial time. Can you provide examples of solvable problems not verifiable in polynomial time ? Asked By : user533933 Answered By : Raphael Given input $x = langle M Read More …
[Solved]: Haskell monad bind operator type
Problem Detail: In Haskell, the Monads type class has the bind operator, which is represented by the symbol >>= The type of such operator is: (>>=) :: Monad m => m a -> (a -> m b) -> m b Why Read More …
[Solved]: Compute ‘permutation’ like problem with modulo
Problem Detail: Say, I have some permutation or combination formula like this, $$frac{n!}{(n-r)!r!},$$ and I want to $bmod$ the result with some big prime ($10^9+7$ for example). I already tried with modular operation and multiplicative inverse but failed (I don’t quite Read More …
[Solved]: Is this pumping lemma proof correct?
Problem Detail: $$ L = {a^ib^jc^k mid i,j,k > 0 text{ and } i+k>j} $$ I say it’s not regular. Proof by pumping lemma: Find a string $xy^iz$ that is not in $L$ (respecting the constraints). Let $w=x^py^pz^p$. Let $i=2$. $x^p(y^py^p)z^p$ Read More …
[Solved]: Intuitive meaning of modal $mu$-calculus formula
Problem Detail: I am solving one of the past exams and I am not certain with my solution to one of the exercises. The exercise is asking to give intuitive meaning to modal $mu$-calculus formula: $$ phi = mu Z. langle Read More …
