Problem Detail: We’re in a shared memory concurrency model where all reads and writes to integer variables are atomic. do: $S_1$ in parallel with: $S_2$ means to execute $S_1$ and $S_2$ in separate threads, concurrently. atomically($E$) means to evaluate $E$ Read More …
Author: ignougroup
[Solved]: Is $A={ w in {a,b,c}^* mid #_a(w)+ 2#_b(w) = 3#_c(w)}$ a CFG?
Problem Detail: I wonder whether the following language is a context free language: $$A = {w in {a,b,c}^* mid #_a(w) + 2#_b(w) = 3#c(w)}$$ where $#_x(w)$ is the number of occurrences of $x$ in $w$. I can’t find any word that Read More …
[Solved]: Perfectly Secure Ciphers known other than the OTP
Problem Detail: By Information-Theoretic definitions, the One Time Pad (OTP) is called/was proved to be a Perfectly Secure Cipher. For the sake of completeness, we define OTP: An enc/dec function, $f:mathcal{P} times mathcal{K} rightarrow mathcal{C}$ Perfect Security: Given $m, m^* in Read More …
[Solved]: What is the difference between these terms?
Problem Detail: Between my textbook and various online sources (namely wikipedia), I’m very confused… can somebody clear up which words are synonymous and which mean different things? Many-to-one reduction Mapping reduction Turing reduction Cook reduction Karp reduction Polynomial-time many-to-one reduction Polynomial Read More …
[Solved]: the height of a tree given n nodes and a condition
Problem Detail: I came across a question on which I got totally stuck 🙁 a sort of homework question) A weight-balanced tree is a binary tree in which for each node. The number of nodes in the left sub tree is Read More …
[Solved]: Must a complete subgraph be induced?
Problem Detail: If we had some $K_n$ subgraph where $K_n subseteq G$, must the complete subgraph $K_n$ be an induced subgraph from $G$? In other words, can we create a situation where we remove vertices from a simple graph $G$ to Read More …
[Solved]: Modelling a basic sequential circuit as a transition system?
Problem Detail: I’m going through Dr Joost-Pieter Katoen’s slides and stumbled upon this: For some reason I can’t quite make out how the transition system relates to the sequential circuit. If I had a question for instance that asked me to Read More …
[Solved]: Why is this argument for $Pneq NP$ wrong?
Problem Detail: I know its silly, but i managed to confuse myself and i need help settling this Suppose $P=NP$, then clearly for every oracle $A$ we have $P^A=NP^A$ which contradicts the fact that there exists some oracle $A$ for which Read More …
[Solved]: Is there a way to compute time without system clock
Problem Detail: I was thinking about any method where we can use RAM I/O speed, to calculate time, let’s say for example: RAM transfer rate is 1000 MB/s, so when it’s half full (about 500 M Bytes written), by dividing 500 Read More …
[Solved]: How can you bound the error of an approximation without knowing the optimal solution?
Problem Detail: I been looking at this site and it says that people found solutions for TSP tours that are just 0.031% higher than the optimal tour is. Without finding the optimal tour how does they know what length it is Read More …
