Problem Detail: I’m reading The Art of Multiprocessor Programming and am currently trying to understand Chapter 4 — The Foundations of Shared Memory. In section 4.2 it is shown how to build a multi-reader, single-writer (MRSW) safe Boolean register from a Read More …
Blog
[Solved]: Why is the set of NFA that accept all words in co-NPSPACE?
Problem Detail: In Sipser’s book there is a section describing how to decide $qquaddisplaystyle mathrm{ALL}_mathrm{NFA} = { langle N rangle mid N text{ is an NFA}, L(N) = Sigma^*}$ in polynomial space. To do so, it shows $overline{mathrm{ALL}_mathrm{NFA} }$ is in Read More …
[Solved]: Natural occurrences of monads that make use of the category-theoretical framework
Problem Detail: Today, a talk by Henning Kerstan (“Trace Semantics for Probabilistic Transition Systems”) confronted me with category theory for the first time. He has built a theoretical framework for describing probablistic transition systems and their behaviour in a general way, Read More …
[Solved]: Hardness of Approximating 0-1 Integer Programs
Problem Detail: Given a $0,1$ (binary) integer program of the form: $$ begin{array}{lll} text{min} & f(x) & text{s.t.} &Avec{x} = vec{b} & quad forall i &x_ige 0 & quad forall i &x_i in {0,1} & quad forall i end{array} $$ Note: Read More …
[Solved]: Why is $(log(n))^{99} = o(n^{frac{1}{99}})$
Problem Detail: I am trying to find out why $(log(n))^{99} = o(n^{frac{1}{99}})$. I tried to find the limit as this fraction goes to zero. $$ lim_{n to infty} frac{ (log(n))^{99} }{n^{frac{1}{99}}} $$ But I’m not sure how I can reduce this Read More …
[Solved]: Binary decision diagram for a six-figure Boolean function
Problem Detail: Let $p$ be the six-figure Boolean function with the following definition: $p(x_{0},x_{1},x_{2},x_{3},x_{4},x_{5})=begin{cases} true & text{if } x_{0}=x_{5} text{ and } x_{1}=x_{4} text{ and } x_{2}=x_{3}, false & text{else.} end{cases}$ This function obviously yields $true$ iff $x_{0}x_{1}x_{2}x_{3}x_{4}x_{5}$ is a Read More …
[Solved]: Lossless data compression must make some messages longer?
Problem Detail: I read on Wikipedia and in lecture notes that if a lossless data compression algorithm makes a message shorter, it must make another message longer. E.g. In this set of notes, it says: Consider, for example, the 8 possible Read More …
[Solved]: Bayesian Network – Inference
Problem Detail: I have the following Bayesian Network and need help with answering the following query. EDITED: Here are my solutions to questions a and b: a) P(A,B,C,D,E) = P(A) * P(B) * P(C | A, B) * P(D | E) Read More …
[Solved]: How do I explain that a polynomial time reduction is in fact polynomial time?
Problem Detail: I have as an assignment question to show that $QuadSat={langlephiranglemidphi$ is a satisfiable 3CNF formula with at least 4 satisfying assignments$}$ is $sf NP$-Complete. My solution is as follows, which is pretty much copied almost 100% from a textbook Read More …
[Solved]: Prove Σ* is decidable
Problem Detail: I see that Σ* is claimed to be decidable in many documents, but I have never seen an example or easy demostration that it is decidable. What is the proof that Σ* is decidable? Asked By : Charles Answered By Read More …
