2022 Developer Survey is open! Take survey.

Questions tagged [definitions]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
2 answers
42 views

Formal definition of algorithm runtime

In the analysis of algorithms textbooks that I've seen, as far as I could tell, the runtime of an algorithm is defined intuitively. Is there a simple formal definition of this concept? I.e. a ...
user avatar
  • 3,464
0 votes
0 answers
17 views

Definition of the term "access efficiency" in the context of computer systems

In a two-level virtual memory, the memory access time for main memory, $t_M=10^{−8}$ sec, and the memory access time for the secondary memory, $t_D=10^{−3}$ sec. What must be the hit ratio, $H$ such ...
user avatar
1 vote
1 answer
34 views

Probabilistic Turing Machine Transition Relation vs Transition Function

In wiki, PTM are defined with two transition functions and a fair coin toss which determines which one is used at each step. One can also define them, much like NDTM, using a transition relation where ...
user avatar
0 votes
0 answers
20 views

Is there any problems with equating Turing Machines with Algorithms and Language with Problems?

In a lot of the online explanation of complexity theory, the author proposes the following. "The definition associated with complexity theory (e.g., definition of NP) is phrased in terms of ...
user avatar
2 votes
0 answers
36 views

Regarding the definitions of time-constructible functions on Wikipedia

I am reading the Wikipedia article on time-constructible functions and got confused by its definitions, given as follows: There are two different definitions of a time-constructible function. In the ...
user avatar
  • 423
0 votes
1 answer
15 views

Same instances for different problems

According to the formal definition of an instance, it is a set of input data containing the values of the parameters of some problem (What is an instance of NP complete problem?). So, two problems may ...
user avatar
  • 103
0 votes
0 answers
9 views

Explain how a text retrieval db & query differs from a document db and query and which do I need?

To any and all, I am in need of either a text retrieval database, a document database, a hybrid database, something custom, or perhaps something else. I am asking for someone to explain the ...
user avatar
0 votes
2 answers
46 views

What's the error about the definition of NP?

Many sources (including Wolfram's MathWorld) say that NP problem is defined as a decision problem "verifiable in nondeterministic polynomial time" (check Google to see more sources). But ...
user avatar
  • 413
0 votes
2 answers
222 views

What defines how many lookahead a lexer has?

if a lexical grammar has multiple token which start with the same character like > >> ...
user avatar
  • 1
0 votes
1 answer
41 views

Having trouble understanding blatantly non-private definition because of Little-o notation

I was pretty confident that I understand asymptotic notation until now. However, I am having a hard time understanding some basic definition that use asymptotic notation, specially little-o. ...
user avatar
  • 3
1 vote
0 answers
30 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 ...
user avatar
1 vote
1 answer
52 views

Can inputs in the decision tree model be computed?

The Wikipedia definition of the decision tree model says that it allows the sign functions of certain classes to be computed in constant time (and presumably also memory). My questions, still ...
user avatar
  • 113
2 votes
1 answer
41 views

On the definition of Error-Correcting Codes

Let us start with the following well-known definition: Definition 1. Let $C\subseteq A^n$ be a code over $A$ and let $t\in \Bbb Z^+$ be a positive integer. We say that the code $C$ is $\boldsymbol t$...
user avatar
  • 123
0 votes
1 answer
32 views

Isn't an improper subset of edges of a cyclic graph, cyclic and thus not a minimum spanning tree?

This is the formal definition of a minimum spanning tree taken from Algorithms by Dasgupta, Papadimitrious and U. Vazirani. Input: An undirected graph $G = (V,E)$; edge weights $w_e$. Output: A tree $...
user avatar
0 votes
2 answers
50 views

PRECISE DPLL algorithm definition

I am confused about the precise definition of the DPLL algorithm. Various sources tend to define DPLL differently: In pages 110-114 of the book Handbook of Satisfiability(Editors: Biere, A., Heule, M....
user avatar
1 vote
1 answer
38 views

Equivalene of big O definitions (Limit Definition $\Longleftrightarrow$ Quantifier Definition)

I need to proof, that both definitions of the Big 0 notation are equiavlent, but I am not sure if my proof works both ways of the equivalence. Definitions: Let f,g be functions. $f(n)\in \mathcal{O}(...
user avatar
2 votes
1 answer
70 views

What is the difference between Hamming Distance and Manhattan Distance for non-binary data?

What is the difference between Hamming Distance and Manhattan Distance for non-binary data (specifically I am comparing points in $\mathbb{R}^2$)? I understand Manhattan sums the absolute difference ...
user avatar
  • 123
0 votes
0 answers
28 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 ...
user avatar
  • 45
2 votes
1 answer
55 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 ...
user avatar
  • 393
1 vote
0 answers
36 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 ...
user avatar
  • 243
4 votes
0 answers
77 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 ...
user avatar
2 votes
2 answers
483 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-...
user avatar
1 vote
1 answer
186 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 ...
user avatar
  • 113
1 vote
1 answer
81 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 ...
user avatar
  • 707
1 vote
1 answer
125 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 ...
user avatar
0 votes
1 answer
74 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 ...
user avatar
1 vote
1 answer
57 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 ...
user avatar
  • 423
17 votes
11 answers
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: ...
user avatar
  • 307
0 votes
1 answer
102 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 ...
user avatar
1 vote
1 answer
758 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 ...
user avatar
3 votes
0 answers
51 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 ...
user avatar
1 vote
0 answers
35 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) ...
user avatar
  • 374
6 votes
3 answers
1k 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,...
user avatar
  • 4,009