Questions tagged [definitions]

The tag has no usage guidance.

7 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4
votes
0answers
57 views

Understanding the Transition points of a BST

I'm trying to understand the definition of Transition point of a BST, as given in Demaine, Erik D., et al. "Dynamic optimality-almost." SIAM Journal on Computing 37.1 (2007): 240-251 ...
3
votes
0answers
48 views

What is the name of visiting an array starting at first element, then last element, then second, then last but one, then third, etc

For example if I have an array [0, 1, 2, 3, 4, ..., n] and I want to iterate over it in an order like ...
1
vote
0answers
17 views

Language of all words of the form $ww$ is in $\mathsf{NTIME}(n)$

Show that the language $\{ ww \mid w \in \{0,1\}^* \}$ is in $\mathsf{NTIME}(n)$. I have a doubt first of all how can I prove that. Secondly, what does NTIME mean? Can we use a $k$-Tape Turing ...
1
vote
0answers
31 views

A genral Turing model with one tape to define sublinear space (L,NL,..)

A genral Turing model with one tape to define sublinear space (L,NL,..) Normally to define sub-linear space complexity we need special Turing models with many tapes, at least two: a read-only tape and ...
1
vote
0answers
32 views

Randomized version of the class $APX$?

Is there a class which is to APX what BPP is to P? I'm looking for a definition that is like the following: "For $r > 0$, an $r$-RPCA (randomized polynomial-time constant-factor approximation) ...
0
votes
0answers
24 views

How isolate the last bit work on teory Binary Indexed Trees

I'm learning about the Binary Indexed Trees, and I understand how it works, but I'm interested in the theory that there is behind! In particular, I don't understand what is meant the following ...
0
votes
0answers
16 views

Informal definition of a safety property

Could someone kindly explain why safety properties are commonly informally described as "something bad never happens"? This doesn't seem accurate at all. Rather, it seems that one should say ...