Problem Detail: Please forgive me for asking a novice question, but I’m a beginner at algorithms and complexities, and it’s sometimes hard to understand how the complexity for a specific algorithm has come about. I was reading the DFS algorithm from Read More …
Blog
[Solved]: median filter one after the other
Problem Detail: Operate on an image by performing Median Filtering in a 3×3 window. Operate on the resulting image by performing, again, Median Filtering in a 3×3 window. Can the resulting image be obtained from a single Median filtering? my initial Read More …
[Solved]: Clarifications on polynomial reducibility for problems in P and NP-complete
Problem Detail: Can I always increase the complexity of a problem via polynomial reduction? (in which case ‘reduction‘ is really a misnomer) For example, if I have a classic P problem (say, finding the smallest element in an array, by iterating Read More …
[Solved]: Turing reducibility implies mapping reducibility
Problem Detail: The question is whether the following statement is true or false: $A leq_T B implies A leq_m B$ I know that if $A leq_T B$ then there is an oracle which can decide A relative to B. I know Read More …
[Solved]: Proving that context-free languages are closed under inserting symbols
Problem Detail: This is a theoretical computer science question, regarding the proof of whether or not context-free languages are closed under an operation. This means basically that any context-free language which undergoes this operation would still be context-free. For a language Read More …
[Solved]: Decision problems in $mathsf{P}$ without fast algorithms
Problem Detail: What are some examples of difficult decision problems that can be solved in polynomial time? I’m looking for problems for which the optimal algorithm is “slow”, or problems for which the fastest known algorithm is “slow”. Here are two Read More …
[Solved]: Constructing an unrestricted grammar for a^n b^m c^n d^m
Problem Detail: I’ve been trying to construct an unrestricted grammar which has the language: L = {a^n b^m c^n d^m | n>0, m>0} But I can’t seem to figure it out without making the derivations run an unreasonably long amount of Read More …
[Solved]: Where is the recursion, in the minimax-decision algorithm?
Problem Detail: The below is from an article titled: Minimax: Recursive Implementation To be a recursive function, you need to call yourself. What part of this pseudo code is calling itself? How does depth-first effect the recursion process? There seems to Read More …
[Solved]: Testing whether the language of one automaton is a subset of another
Problem Detail: Is there an algorithm to solve following problem? Given two finite automata $A$ and $B$. Determine whether the language recognized by automaton $A$ is a subset of language recognized by automaton $B$ or otherwise. Asked By : Jendas Answered By Read More …
[Solved]: Why can’t I run a mac program natively on windows?
Problem Detail: Basically, I believe that if you have something like a .dmg file the OS opens it with a certain program which takes the code behind it and does things to it. So why couldn’t you then take the program Read More …
