Questions tagged [definitions]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
21 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 ...
2
votes
1answer
29 views

Why are $L$-reductions defined the way they are?

I was reading about $L$-reductions and there was one part in the definition that I thought was interesting. I wanted to know what motivated people who came up with it to have it included in the ...
1
vote
0answers
25 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 ...
4
votes
0answers
54 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 ...
2
votes
2answers
424 views

Definition of NP-hardness for non-decision problems

As I understand, the term "NP-hardness" is applicable when we also talk about optimization or search problems (i.e. return the satisfying assignment for 3-SAT). How do we formally define NP-...
0
votes
0answers
14 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 ...
1
vote
1answer
47 views

Nondeterministic polynomial time algorithm versus certificate/verifier for showing membership in NP

In this paper (https://arxiv.org/pdf/1706.06708.pdf) the authors prove that optimally solving the $n\times n\times n$ Rubik's Cube is an NP-complete problem. In the process, they must show that the ...
1
vote
1answer
29 views

A question regarding definition of Deterministic Subexponential Time (SUBEXP)

First Look at the definition of SUBEXP from Complexity Zoo: SUBEXP: (Deterministic Subexponential-Time) The intersection of DTIME($2^{n^\epsilon}$) over all $\epsilon$>0. (Note that the algorithm ...
1
vote
1answer
62 views

Sets in Mathematics are immutable but in Computer Science sets are mutable and called “Dynamic Sets” - truth of the statement

While reading the classic text Introduction to Algorithms by Cormen et. al. I came across the following claim: Sets are as fundamental to computer science as they are to mathematics. Whereas ...
1
vote
1answer
20 views

Clarifying statements involving asymptotic notations in soln of $T(n) = 3T(\lfloor n/4 \rfloor) + \Theta(n^2)$ using recursion tree and substitution

Below is a problem worked out in the Introduction to Algorithms by Cormen et. al. (I am not having problem with the proof but only I want to clarify the meaning conveyed by few statements in the text ...
1
vote
1answer
29 views

When does a Monte Carlo algorithm solve a problem?

When can we say that a Monte Carlo algorithm solves a problem? To quote from Wikipedia on Monte Carlo algorithms For instance, the Solovay–Strassen primality test is used to determine whether a ...
17
votes
11answers
5k views

Why do logic gates behave the way they do?

I am a Software Developer but I came from a non-CS background so maybe it is a wrong question to ask, but I do not get why logic gates/boolean logic behave the way they do. Why for example: ...
0
votes
1answer
29 views

Formal definition of hash function

I was reading through the classic CLRS with the intention of reviewing the hash tables theory, more specifically the hash function definition I just wanted a reference to quote. I cannot find a ...
1
vote
1answer
286 views

Difference between task and process

I'd like to know which is the difference between a task and a process in computer science. I'm studying a course on real-time systems and there are some definitions that I don't know. Thank you in ...
3
votes
0answers
47 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
30 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) ...
6
votes
3answers
482 views

Simple cycles of length two in an undirected graph

Pedagogical question. Background A cycle in a graph can be defined as a sequence of vertices $v_1,\dots,v_n$ with $v_1=v_n$ such that, for each $i \in \{1,\dots,n-1\}$, the graph has an edge $(v_i,...