Search type Search syntax
Tags [tag]
Exact "words here"
Author user:1234
user:me (yours)
Score score:3 (3+)
score:0 (none)
Answers answers:3 (3+)
answers:0 (none)
isaccepted:yes
hasaccepted:no
inquestion:1234
Views views:250
Sections title:apples
body:"apples oranges"
URL url:"*.example.com"
Favorites infavorites:mine
infavorites:1234
Status closed:yes
duplicate:no
migrated:no
wiki:no
Types is:question
is:answer
Exclude -[tag]
-apples
For more details on advanced search visit our help page
Results tagged with Search options user 81319

Questions related to the (computational) complexity of solving problems

0
votes
Let $L_{1}$={Set Of All Regular Languages}, $L_{2}\cup L_{3}$= $\bar{L}_{1}$ $L_{2}$={Set Of All Non Regular Languages That Are Recognizable By Turing Machines.} $L_{1}$ is Decidable, $L_{2}$ Recog …
answered Mar 11 '18 by Anwar Saiah
0
votes
1answer
A perfect natural number is that which is equal to the sum of it's divisors. For example 6 is perfect: 1+2+3=6 also 28 is perfect. Prove the following language is NP hard: L={< n> | n is a perfect …
asked Feb 3 '18 by Anwar Saiah
-1
votes
1answer
$\sum$ is the Alphabet of three infinite languages $L_{1},L_{2}$ and $L_{3}$ where $L_{1}\cup L_{2} \cup L_{3}=\sum^{*}$ and $L_{1} \cap L_{2} = \emptyset$, $L_{2} \cap L_{3} =\emptyset$ and $L …
asked Mar 10 '18 by Anwar Saiah
0
votes
Given M, construct in o(1) time a DFA M' that accepts all odd length words in M's language, basically a DFA with two states. Construct a product DFA M'' from M and M'. Check if L(M'') is empty, if so …
answered Jan 21 '18 by Anwar Saiah
1
vote
2answers
Would this proof work? Given a language $L$ that is Turing recognizable and a TM M that recognizes it and a homomorphism $f$, we build a NTM M' that recognizes $f(L)$, M' looks like this: On input …
asked Feb 4 '18 by Anwar Saiah
1
vote
1answer
Let MULT$=\{a\#b\#c| a,b,c \text{ binary natural numbers and } a\times b=c\}$ Prove that MULT $\in L$ How do I show that this language, MULT, is computable in Logarithmic space? Let us assume a#b#c …
asked Feb 4 '18 by Anwar Saiah
2
votes
3answers
L={ | M is a DFA, |w| is even for all w in L(M)} Meaning we are looking for a Turing Machine or any algorithm that receives a description of a DFA and decides if all the words this DFA accepts are ev …
asked Jan 15 '18 by Anwar Saiah
1
vote
1answer
Does every language $C$ in the class $BPP$ have a mapping reduction to $A_{TM}$? $(C\leq _{m} A_{TM})$ $BPP$ is the class of languages that have a probabilistic $TM$ that accepts them with an error $ …
asked Mar 15 '18 by Anwar Saiah
0
votes
Since no answer has been posted I will attempt the answer my self: Since Giacomo explained why $L$ is TR(I thank him for that) I won't talk about it. I will prove $L$ is not decidable: We do that by …
answered Aug 25 '18 by Anwar Saiah
0
votes
0answers
$E_{TM}=$ { < $M$> $|$ $M$ is a TM; $L(M)$=$\varnothing$} Where $L(M)$ is the language accepted(recognized) by $M$. $OVERLAP_{TM}=$ {< $M_{1}$,$M_{2}$> $|$ $M_{1}$,$M_{2}$ are TMs; $L(M_{1})\cap L( …
asked Aug 26 '18 by Anwar Saiah
0
votes
1answer
where $L_{1} \cup L_{2} \cup L_{3} = \sum^{*}$ and $L_{1} \cap L_{2} = \emptyset$ and $L_{2} \cap L_{3} = \emptyset$ and $L_{1} \cap L_{3} = \emptyset$ is it possible that $L_{1}$ is decidable, $L_ …
asked Mar 10 '18 by Anwar Saiah
1
vote
2answers
Given two NP-Complete languages A and B, show that the language: $L = A\bigoplus B =\{a\bigoplus b \mid a \in A, b \in B, |a|=|b|\}$ is not necessarily NP-Complete. Remember $a\bigoplus b$ when $| …
asked Mar 2 '18 by Anwar Saiah
1
vote
1answer
How would I reduce $A_{TM}$ to $CF_{TM}$ when: $A_{TM}=\{<M,w>|M$ is a Turing Machine description and $w\in L(M)\} $ $CF_{TM} =\{<M> | M$ is a Turing Machine description $L(M)$ is a context-free lan …
asked Mar 20 '18 by Anwar Saiah
1
vote
1answer
If both $A$ and $B$ are NP-complete languages, would $A \times B$ be necessarily NP-hard? Here, $A \times B = \{\langle u,v \rangle \mid u\in A, v\in B\}$. So my colleague's answer was no, it's not …
asked Mar 25 '18 by Anwar Saiah
1
vote
1answer
$M=(Q,\sum,\Gamma, \delta, q_{0}, q_{accept}, q_{reject})$ is a TM with one tape. let $c_{1}, c_{2}$ be two configurations of $M$. A configuration is defined like this: $uqv$ where $(q\in Q; u,v\i …
asked Aug 24 '18 by Anwar Saiah

15 30 50 per page