Problem Detail: Let $A$ and $B$ be Turing-recognizable languages. Must language $C = A cap B$ be Turing-recognizable too? I have a hunch that it should be because we can construct an enumerator for $C$ by enumerating all the languages in Read More …
Category: Uncategorized
Why unsafe state not always cause deadlock?
Problem Detail: I was reading Operating Systems by Galvin and came across the below line, Not all unsafe states are deadlock, however. An unsafe state may lead to deadlock Can someone please explain how deadlock != unsafe state ? I also Read More …
Moore’s law and Clock Speed
Problem Detail: This figure says according to moore’s law number of transistors doubles about two years. but clock speed, power flattening after given stage. can anyone describe the reasons this flattening in clock-speed. Why can’t we increase the clock speed Read More …
Checking if there are 2 elements in an array that sum to X in O(n lg n)
Problem Detail: I have thought about the most useful way of checking an array for 2 elements that sum to X. The trivial solution is to check the sum of every element with every element, and the complexity of this solution Read More …
What is the relationship between NP/NP-Complete/NP-Hard to time complexity?
Problem Detail: I’m familiar with a few problems of each class and even though the definitions are based on sets and polynomial reducibility, I see a pattern with time complexity. NP problems appear to be $O(2^n)$ (minus the P problems of Read More …
Why is C’s void type not analogous to the empty/bottom type?
Problem Detail: Wikipedia as well as other sources that I have found list C’s void type as a unit type as opposed to an empty type. I find this confusing as it seems to me that void better fits the definition Read More …
Why are there more non-computable functions than computable ones?
Problem Detail: I’m currently reading a book in algorithms and complexity. At the moment I’m, reading about computable and non-computable functions, and my book states that there are many more functions that are non-computable than computable, in fact the majority is Read More …
Dynamic programming with large number of subproblems
Problem Detail: Dynamic programming with large number of subproblems. So I’m trying to solve this problem from Interview Street: Grid Walking (Score 50 points) You are situated in an $N$-dimensional grid at position $(x_1,x_2,dots,x_N)$. The dimensions of the grid are $(D_1,D_2,dots,D_N$). Read More …
Context-free grammar for ${ a^n b^m a^{n+m} }$
Problem Detail: I’ve got a problem with this task. I should declare a context-free grammar for this language: $qquad displaystyle L := {, a^nb^ma^{n+m} : n,m in mathbb{N},}$ My idea is: We need a start symbol, for example $S$. I know Read More …
How to prove that a constrained version of 3SAT in which no literal can occur more than once, is solvable in polynomial time?
Problem Detail: I’m trying to work out an assignment (taken from the book Algorithms – by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, Chap 8, problem 8.6a), and I’m paraphrasing what it states: Given that 3SAT remains NP-complete even when restricted Read More …
