Questions tagged [check-my-answer]
Questions asking us to check whether your solution is correct only are considered off-topic (per http://meta.cs.stackexchange.com/questions/597/). Please pinpoint your doubt and provide *a specific question* to which a meaty answer can resolve your doubt whether your answer is correct or not.
137 questions
1
vote
1
answer
136
views
Runtime for the unordered "Errands" problem
Consider the following problem:
Let $G=(V, E)$ be a weighted undirected graph with nonnegative weights. Let $S_1, S_2, \ldots, S_k\subseteq V$ be disjoint subsets representing vertices where you can ...
- 63
1
vote
0
answers
46
views
I wanted to verify wether my counterexample for proving that CFLs are closed under Perfect shuffle is indeed correct
I wanted to verify whether my counter-example for proving that CFLs are not closed under Perfect shuffle is indeed correct. I just want to know if the counter-example is correct, I know the proof can ...
- 111
1
vote
0
answers
64
views
How can I show these two expressions for the the product of Church numerals are equivalent?
Given this implementation of the addition of Church numerals,
plus = λm. λn. λs. λz. m s (n s z)
and this first implementation of the product, that builds on top ...
- 149
0
votes
1
answer
67
views
Show that there is also a randomized polynomial-time decider $M'$ for $L$ such that $w\in L \Rightarrow Pr[M(w)=1] > 0.99$
The question is suppose there is a randomized polynomial-time decider $M$ for a language $L$ such that:
$w\in L \Rightarrow Pr[M(w)=1]>0.1$
$w\not\in L \Rightarrow Pr[M(w)=1]=0 $
Show that there ...
- 7
0
votes
0
answers
112
views
Can the baseball card collector problem be used to solve Rudrata/Hamiltonian Path? Asking for NP Complete proof
The baseball card collector problem is as follows:
Given packets P1,....., Pm each of which contains a subset of this year's baseball cards, is it possible to collect all the year's cards by buying at ...
0
votes
0
answers
62
views
Prove L is not Büchi-recognisable
I have a question which I would like to check if my proof is valid for:
Let $\Sigma$ be an alphabet consisting of at least two different symbols, and let L be the following
$\omega$-language:
$\{\...
1
vote
1
answer
216
views
Whether $\textbf{PH}$ collapses to $\Sigma^p_1$ when $\overline{3SAT}\in \textbf{BP$\cdot$NP}$
I'm doing ex. 7.8 in Arora and Barak
Show that if $\overline{3SAT}\in \textbf{BP$\cdot$NP}$, then $\textbf{PH}$ collapses to $\Sigma_3^p$.
This is definition of $\textbf{NP}/poly$:
A ...
- 651
1
vote
0
answers
64
views
Prove that $\textbf{NC}$ circuit family can compute log space reduction
Most proofs of the problem that I have seen stop at proving $\textbf{NL}\subseteq \textbf{NC}^2$ and not explicitly point out the circuit. I'm trying to show that $\textbf{NC}$ circuit family can ...
- 651
2
votes
0
answers
72
views
Proving that for every semi-Thue system $\Gamma$, there exists a two-letter semi-Thue system $\Gamma'$ such that $S_\Gamma = S_{\Gamma'}$
I'm reading Martin Davis' Computabilty and Unsolvability. In Chapter 6, Section 1, Davis writes the following:
THEOREM 1.8. For every semi-Thue system $\Gamma$, we can construct a semi-Thue system $\...
- 21
3
votes
1
answer
398
views
Minimum number of oracle call to solve Simon problem by a (NDTM) non-deterministic Turing machine?
Simon's problem is a computational problem used to demonstrate an oracle separation between BQP and BPP classes.
It is known that the minimum number of oracle calls to be made by the BQP machine is $\...
- 229
-1
votes
1
answer
109
views
What is the the maximum and minimum amount of nodes in a heap
The title of my question says all that is needed. Some may argue that this is a duplicate question, because some years ago, this same question was made, but I couldn't understand the explanation, then ...
0
votes
2
answers
102
views
Help regarding a proof in which i am able to prove a regular language $(a(a+b)*)$ as irregular using pumping lemma
I have a regular language $a(a+b)^*$ to which i applied pumping lemma.
Let the pumping length be $'p'$
and the example string be $$w=a(a+b)^{p-1}$$.
The string satisfies the condition that it is at ...
- 3
1
vote
1
answer
119
views
Decide if some DFA is accepted
Given Some(DFA) = {|A is a DFA and L(A) is not empty and L(A) is not equal to Σ^(*)}
Show Some(DFA) is decidable.
I produced the following answer and wanted to check if I am correct
T="On input ...
- 11
-1
votes
1
answer
73
views
is my attempt correct? proof that L in P or in NPC? $L=\{G$ is an undirected graph on n vertices VC $U$ and an IS $I$ such that $|U|+|I|=n+10$ \}
I am facing a problem with the validity of the reduction function, may I get some assist in solving this issue, please?
$L=\{<G>| G$ is an undirected graph on n vertices that has a Vertex Cover $...
- 201
0
votes
0
answers
323
views
Interval scheduling; sort by ending times
You have $n$ events on your calendar, defined as intervals with a start time $s_i$ and a finish time $f_i$.
The events might overlap, and you want to attend all the events, so you are going to create $k$...
- 9