Problem Detail: Can someone help me understand the steps in this argument? There is a decision problem that is in $mathsf{cotext{-}NP}$ (under standard Karp reductions) and is $mathsf{NP}$-hard with respect to Cook reductions. Does this imply that if it is in Read More …
Category: Uncategorized
[Solved]: Wiring Length Minimization
Problem Detail: My Problem is like this: I have a physical layout represented as a graph. The Nodes represents hooks/ducts where a wire can anchor and Edges are the possible connection between 2 nodes from where wire can go. There are Read More …
[Solved]: Enumerating all n-tuples over a finite domain
Problem Detail: I would like to create an algorithm which takes in an integer n and returns an array whose entries give all n-tuples of nonnegative integers each of which is at most n, so like A[n][0] = [0,0,0,…,0], A[n][1] = Read More …
[Solved]: Is there a complexity viewpoint of Galois’ theorem?
Problem Detail: Galois’s theorem effectively says that one cannot express the roots of a polynomial of degree >= 5 using rational functions of coefficients and radicals – can’t this be read to be saying that given a polynomial there is Read More …
[Solved]: Why we use context-free grammar for parsing?
Problem Detail: Why we use context-free grammar for parsing? Why not regular expression and not context-sensitive grammar? Asked By : Himanshu Saini Answered By : David Richerby Because regular expressions are too weak and context-sensitive languages are too difficult to parse. More specifically, Read More …
[Solved]: Is the image of a total, non-decreasing function decidable?
Problem Detail: This is an exercise I’ve been struggling with for a while: Let $g : mathbb{N} to mathbb{N}$ be a total, non-decreasing function, i.e. $forall x > y. g(x) geq g(y)$. Is the image $I_g$ of $g$ a recursive set? Read More …
[Solved]: Non-trivial runs of Prim’s algorithm
Problem Detail: What does it mean when we say that a run of Prim’s algorithm is trivial? What are example graphs for either case, that is with and without trivial runs? Asked By : fudu Answered By : Raphael Prim’s algorithm greedily chooses Read More …
[Solved]: If $f(n) = Theta(g(n))$, do both functions bound each other for all $n$ or only sufficiently large $n$?
Problem Detail: The following is an excerpt from CLRS: $Theta(g(n))= { f(n) mid text{ $exists c_1,c_2,n_0>0$ such that $0 le c_1 g(n) le f(n) le c_2g(n)$ for all $n ge n_0$}}$. Assuming $n in mathbb{N}$, I was unable to find $f(n)$ Read More …
[Solved]: Complements of Linear Bounded Automata?
Problem Detail: Would switching the accept and reject states of an LBA A create a new LBA we’ll say A’ in which the language of A’ is the complement of the language of A? I believe the answer is yes just Read More …
[Solved]: Time complexity of proximity search in distance matrix
Problem Detail: I am a high school student computationally studying the 3-dimensional structure of chromosomes by 40 kilobase loci. In a nutshell, loci that are close in space tend to express their genes at the same time ― loci are different Read More …
