All Questions
8 questions
0
votes
0
answers
93
views
Efficient Algorithm To Find A Path Which Covers Maximum Area Along Polygonal Perimeter For Surveillance Application
In the context of surveillance, I am working on a project where the goal is to find an algorithm that determines a path along a polygonal area, connecting a root node to a target node, while ...
- 3
0
votes
0
answers
46
views
Lower bound for $a^kb^k$ in one-tape TM
For the language
$ L= \{a^kb^k | k \geq 0 \} $
How can i show there is no one-tape Turing Machine that can decide $L$ in less than $O(n\log n)$ time ?
- 368
1
vote
1
answer
93
views
The Turing Machine in the proof of Time Hierarchy Theorem
In the proof of the Time Hierarchy Theorem, Arora and Barak writes:
Consider the following Turing Machine $D$: “On input $x$, run for $|x|^{1.4}$ steps the Universal TM $U$ of Theorem 1.6 to simulate ...
- 13
2
votes
1
answer
190
views
Is SAT a single language or a union of languages?
I know that a language is in NP if a Turing machine can decide the language of its checking relation $\{\text{boolean formula }\#\text{ truth assignment | truth assignment is correct}\}$ in polynomial ...
- 145
3
votes
1
answer
122
views
Why isn't DIV necessarily in P? [duplicate]
In my formal languages class, we discussed DIV, defined as following:
$\mathrm{DIV} = \{\langle a,b\rangle : \text{$a, b \in N$ and $a$ has a divisor $d$ for some $1 < d \leq b$ }\}$
($\langle\...
- 33
2
votes
1
answer
144
views
Definition of complexity classes?
My book uses this definition for the Polynomial complexity class ($L$ is a language over $\{0,1\}$):
$$\mathrm{P} = \left\{L\subseteq\{0,1\}^*\;\middle|\; \begin{array}{l} \text{there exists an ...
- 23
3
votes
1
answer
85
views
Complexity of self-reducible set
I am trying to solve the following problem:
A set $S$ is self-reducible if the following holds: $x \in S$ iff $x = 1$(Base case) or (recursively) $l(x) \in S$ and $r(x) \in S$ where $\left|l(x)\...
- 213
2
votes
1
answer
3k
views
How to show that the complement of a language in $\mathsf P$ is also in $\mathsf P$? [duplicate]
If $L$ is a binary language (that is, $L \subseteq \Sigma = \{0,1\}^∗$) and $\overline{L}$ is the complement of $L$:
How can I show that if $L \in \mathsf P$, then $\overline{L} \in \mathsf P$ as ...
- 125