0
$\begingroup$

I'm trying to prove that the following language is L-complete A is a language where each word is comprised of 0s and 1s & the number of 0's is double that of the number of 1's

So far I've managed to show that it can be solved in log space using a counter that adds 2 for every '1' and deducts 1 for every 0.

I need to prove now that every language in L is predictable logarithmically to A

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Can't make a comment so have to use an answer. It's a well-known fact that every non-trivial language in $L$ is complete under log-space reduction because the reduction could be used to decide the language with only two values for a mapping.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.