text:
TheInfoList

OR:

In computer science, the time complexity is the
computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...
that describes the amount of computer time it takes to run an
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor. Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the worst-case time complexity, which is the maximum amount of time required for inputs of a given size. Less common, and usually specified explicitly, is the average-case complexity, which is the average of the time taken on inputs of a given size (this makes sense because there are only a finite number of possible inputs of a given size). In both cases, the time complexity is generally expressed as a function of the size of the input. Since this function is generally difficult to compute exactly, and the running time for small inputs is usually not consequential, one commonly focuses on the behavior of the complexity when the input size increases—that is, the asymptotic behavior of the complexity. Therefore, the time complexity is commonly expressed using big O notation, typically etc., where is the size in units of
bit The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represented ...
s needed to represent the input. Algorithmic complexities are classified according to the type of function appearing in the big O notation. For example, an algorithm with time complexity $O\left(n\right)$ is a ''linear time algorithm'' and an algorithm with time complexity $O\left(n^\alpha\right)$ for some constant $\alpha > 1$ is a ''polynomial time algorithm''.

# Table of common time complexities

The following table summarizes some classes of commonly encountered time complexities. In the table, , i.e., polynomial in ''x''.

# Constant time

An algorithm is said to be constant time (also written as $O(1)$ time) if the value of $T(n)$ (the complexity of the algorithm) is bounded by a value that does not depend on the size of the input. For example, accessing any single element in an array takes constant time as only one
operation Operation or Operations may refer to: Arts, entertainment and media * ''Operation'' (game), a battery-operated board game that challenges dexterity * Operation (music), a term used in musical set theory * ''Operations'' (magazine), Multi-Ma ...
has to be performed to locate it. In a similar manner, finding the minimal value in an array sorted in ascending order; it is the first element. However, finding the minimal value in an unordered array is not a constant time operation as scanning over each
element Element or elements may refer to: Science * Chemical element, a pure substance of one type of atom * Heating element, a device that generates heat by electrical resistance * Orbital elements, parameters required to identify a specific orbit of o ...
in the array is needed in order to determine the minimal value. Hence it is a linear time operation, taking $O(n)$ time. If the number of elements is known in advance and does not change, however, such an algorithm can still be said to run in constant time. Despite the name "constant time", the running time does not have to be independent of the problem size, but an upper bound for the running time has to be independent of the problem size. For example, the task "exchange the values of and if necessary so that $a \le b$" is called constant time even though the time may depend on whether or not it is already true that $a \le b$. However, there is some constant such that the time required is always ''at most'' . Here are some examples of code fragments that run in constant time: int index = 5; int item = list ndex if (condition true) then perform some operation that runs in constant time else perform some other operation that runs in constant time for i = 1 to 100 for j = 1 to 200 perform some operation that runs in constant time If $T\left(n\right)$ is $O\left(a\right)$, where is any constant value, this is equivalent to and stated in standard notation as $T\left(n\right)$ being $O\left(1\right)$.

# Logarithmic time

An algorithm is said to take logarithmic time when $T\left(n\right) = O\left(\log n\right)$. Since $\log_a n$ and $\log_b n$ are related by a constant multiplier, and such a multiplier is irrelevant to big O classification, the standard usage for logarithmic-time algorithms is $O\left(\log n\right)$ regardless of the base of the logarithm appearing in the expression of . Algorithms taking logarithmic time are commonly found in operations on
binary tree In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary t ...
s or when using
binary search In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the ...
. An $O\left(\log n\right)$ algorithm is considered highly efficient, as the ratio of the number of operations to the size of the input decreases and tends to zero when increases. An algorithm that must access all elements of its input cannot take logarithmic time, as the time taken for reading an input of size is of the order of . An example of logarithmic time is given by dictionary search. Consider a
dictionary A dictionary is a listing of lexemes from the lexicon of one or more specific languages, often arranged alphabetically (or by radical and stroke for ideographic languages), which may include information on definitions, usage, etymologies, pr ...
which contains entries, sorted by alphabetical order. We suppose that, for $1 \le k \le n$, one may access the th entry of the dictionary in a constant time. Let $D\left(k\right)$ denote this th entry. Under these hypotheses, the test to see if a word is in the dictionary may be done in logarithmic time: consider $D\left\left(\left\lfloor \frac \right\rfloor\right\right)$, where $\lfloor\;\rfloor$ denotes the floor function. If $w = D\left\left(\left\lfloor \frac \right\rfloor\right\right)$, then we are done. Else, if $w < D\left\left(\left\lfloor \frac \right\rfloor\right\right)$, continue the search in the same way in the left half of the dictionary, otherwise continue similarly with the right half of the dictionary. This algorithm is similar to the method often used to find an entry in a paper dictionary.

# Polylogarithmic time

An algorithm is said to run in polylogarithmic time if its time $T\left(n\right)$ is $O\bigl\left(\left(\log n\right)^k\bigr\right)$ for some constant . Another way to write this is $O\left(\log^kn\right)$. For example, matrix chain ordering can be solved in polylogarithmic time on a
parallel random-access machine In computer science, a parallel random-access machine (parallel RAM or PRAM) is a shared-memory abstract machine. As its name indicates, the PRAM is intended as the parallel-computing analogy to the random-access machine (RAM) (not to be confus ...
, and a graph can be determined to be planar in a fully dynamic way in $O\left(\log^3n\right)$ time per insert/delete operation.

# Sub-linear time

An algorithm is said to run in sub-linear time (often spelled sublinear time) if $T\left(n\right)=o\left(n\right)$. In particular this includes algorithms with the time complexities defined above. Typical algorithms that are exact and yet run in sub-linear time use parallel processing (as the NC1 matrix determinant calculation does), or alternatively have guaranteed assumptions on the input structure (as the logarithmic time
binary search In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the ...
and many tree maintenance algorithms do). However,
formal language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists o ...
s such as the set of all strings that have a 1-bit in the position indicated by the first $\log n$ bits of the string may depend on every bit of the input and yet be computable in sub-linear time. The specific term ''sublinear time algorithm'' is usually reserved to algorithms that are unlike the above in that they are run over classical serial machine models and are not allowed prior assumptions on the input. They are however allowed to be
randomized In common usage, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence of events, symbols or steps often has no order and does not follow an intelligible pattern or combination. Individual rando ...
, and indeed must be randomized for all but the most trivial of tasks. As such an algorithm must provide an answer without reading the entire input, its particulars heavily depend on the access allowed to the input. Usually for an input that is represented as a binary string $b_1, ..., b_k$ it is assumed that the algorithm can in time $O\left(1\right)$ request and obtain the value of $b_i$ for any . Sub-linear time algorithms are typically randomized, and provide only
approximate An approximation is anything that is intentionally similar but not exactly equal to something else. Etymology and usage The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix ' ...
solutions. In fact, the property of a binary string having only zeros (and no ones) can be easily proved not to be decidable by a (non-approximate) sub-linear time algorithm. Sub-linear time algorithms arise naturally in the investigation of property testing.

# Linear time

An algorithm is said to take linear time, or $O\left(n\right)$ time, if its time complexity is $O\left(n\right)$. Informally, this means that the running time increases at most linearly with the size of the input. More precisely, this means that there is a constant such that the running time is at most $cn$ for every input of size . For example, a procedure that adds up all elements of a list requires time proportional to the length of the list, if the adding time is constant, or, at least, bounded by a constant. Linear time is the best possible time complexity in situations where the algorithm has to sequentially read its entire input. Therefore, much research has been invested into discovering algorithms exhibiting linear time or, at least, nearly linear time. This research includes both software and hardware methods. There are several hardware technologies which exploit parallelism to provide this. An example is
content-addressable memory Content-addressable memory (CAM) is a special type of computer memory used in certain very-high-speed searching applications. It is also known as associative memory or associative storage and compares input search data against a table of stored ...
. This concept of linear time is used in string matching algorithms such as the Boyer–Moore algorithm and Ukkonen's algorithm.

# Quasilinear time

An algorithm is said to run in quasilinear time (also referred to as log-linear time) if $T\left(n\right)=O\left(n\log^kn\right)$ for some positive constant ; linearithmic time is the case $k=1$. Using
soft O notation Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund L ...
these algorithms are $\tilde\left(n\right)$. Quasilinear time algorithms are also $O\left(n^\right)$ for every constant $\epsilon >0$ and thus run faster than any polynomial time algorithm whose time bound includes a term $n^c$ for any $c>1$. Algorithms which run in quasilinear time include: * In-place merge sort, $O\left(n\log^2n\right)$ * Quicksort, $O\left(n\log n\right)$, in its randomized version, has a running time that is $O\left(n\log n\right)$ in expectation on the worst-case input. Its non-randomized version has an $O\left(n\log n\right)$ running time only when considering average case complexity. *
Heapsort In computer science, heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks th ...
, $O\left(n\log n\right)$,
merge sort In computer science, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same ...
,
introsort Introsort or introspective sort is a hybrid sorting algorithm that provides both fast average performance and (asymptotically) optimal worst-case performance. It begins with quicksort, it switches to heapsort when the recursion depth exceeds a le ...
, binary tree sort,
smoothsort In computer science, smoothsort is a comparison-based sorting algorithm. A variant of heapsort, it was invented and published by Edsger Dijkstra in 1981. Like heapsort, smoothsort is an in-place algorithm with an upper bound of , but it is not ...
,
patience sorting In computer science, patience sorting is a sorting algorithm inspired by, and named after, the card game patience. A variant of the algorithm efficiently computes the length of a longest increasing subsequence in a given array. Overview The alg ...
, etc. in the worst case *
Fast Fourier transform A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in t ...
s, $O\left(n\log n\right)$ * Monge array calculation, $O\left(n\log n\right)$ In many cases, the $O\left(n\log n\right)$ running time is simply the result of performing a $\Theta \left(\log n\right)$ operation times (for the notation, see ). For example, binary tree sort creates a
binary tree In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary t ...
by inserting each element of the -sized array one by one. Since the insert operation on a
self-balancing binary search tree In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions. Dona ...
takes $O\left(\log n\right)$ time, the entire algorithm takes $O\left(n\log n\right)$ time.
Comparison sort A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three-way comparison) that determines which of two elements should occ ...
s require at least $\Omega \left(n\log n\right)$ comparisons in the worst case because $\log \left(n!\right)=\Theta \left(n\log n\right)$, by
Stirling's approximation In mathematics, Stirling's approximation (or Stirling's formula) is an approximation for factorials. It is a good approximation, leading to accurate results even for small values of n. It is named after James Stirling, though a related but less ...
. They also frequently arise from the recurrence relation $T(n) = 2T\left(\frac\right)+O(n)$.

An
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
is said to be subquadratic time if $T\left(n\right)=o\left(n^2\right)$. For example, simple, comparison-based
sorting algorithm In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. Efficient sorting is impor ...
s are quadratic (e.g. insertion sort), but more advanced algorithms can be found that are subquadratic (e.g.
shell sort Shellsort, also known as Shell sort or Shell's method, is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort). The method starts by sorting pairs of ...
). No general-purpose sorts run in linear time, but the change from quadratic to sub-quadratic is of great practical importance.

# Polynomial time

An algorithm is said to be of polynomial time if its running time is
upper bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of . Dually, a lower bound or minorant of is defined to be an elem ...
ed by a polynomial expression in the size of the input for the algorithm, that is, for some positive constant ''k''.
Problems A problem is a difficulty which may be resolved by problem solving. Problem(s) or The Problem may also refer to: People * Problem (rapper), (born 1985) American rapper Books * ''Problems'' (Aristotle), an Aristotelian (or pseudo-Aristotelian) c ...
for which a deterministic polynomial-time algorithm exists belong to the complexity class P, which is central in the field of
computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...
. Cobham's thesis states that polynomial time is a synonym for "tractable", "feasible", "efficient", or "fast". Some examples of polynomial-time algorithms: * The
selection sort In computer science, selection sort is an in-place comparison sorting algorithm. It has an O(''n''2) time complexity, which makes it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is no ...
sorting algorithm on ''n'' integers performs $An^2$ operations for some constant ''A''. Thus it runs in time $O\left(n^2\right)$ and is a polynomial-time algorithm. * All the basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) can be done in polynomial time. * Maximum matchings in
graphs Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties * Graph (topology), a topological space resembling a graph in the sense of discr ...
can be found in polynomial time.

## Strongly and weakly polynomial time

In some contexts, especially in
optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
, one differentiates between strongly polynomial time and weakly polynomial time algorithms. These two concepts are only relevant if the inputs to the algorithms consist of integers. Strongly polynomial time is defined in the arithmetic model of computation. In this model of computation the basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) take a unit time step to perform, regardless of the sizes of the operands. The algorithm runs in strongly polynomial time if: # the number of operations in the arithmetic model of computation is bounded by a polynomial in the number of integers in the input instance; and # the space used by the algorithm is bounded by a polynomial in the size of the input. Any algorithm with these two properties can be converted to a polynomial time algorithm by replacing the arithmetic operations by suitable algorithms for performing the arithmetic operations on a
Turing machine A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algo ...
. The second condition is strictly necessary: given the integer $2^n$ (which takes up space proportional to ''n'' in the Turing machine model), it is possible to compute $2^$ with ''n'' multiplications using repeated squaring. However, the space used to represent $2^$ is proportional to $2^n$, and thus exponential rather than polynomial in the space used to represent the input. Hence, it is not possible to carry out this computation in polynomial time on a Turing machine, but it is possible to compute it by polynomially many arithmetic operations. However, for the first condition, there are algorithms that run in a number of Turing machine steps bounded by a polynomial in the length of binary-encoded input, but do not take a number of arithmetic operations bounded by a polynomial in the number of input numbers. The Euclidean algorithm for computing the greatest common divisor of two integers is one example. Given two integers $a$ and $b$, the algorithm performs $O\left(\log a + \log b\right)$ arithmetic operations on numbers with at most $O\left(\log a + \log b\right)$ bits. At the same time, the number of arithmetic operations cannot be bounded by the number of integers in the input (which is constant in this case, there are always only two integers in the input). Due to the latter observation, the algorithm does not run in strongly polynomial time. Its real running time depends ''logarithmically'' on the magnitudes of $a$ and $b$ (that is, on their length in bits) and not only on the number of integers in the input. An algorithm that runs in polynomial time but that is not strongly polynomial is said to run in weakly polynomial time. A well-known example of a problem for which a weakly polynomial-time algorithm is known, but is not known to admit a strongly polynomial-time algorithm, is
linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...
. Weakly polynomial time should not be confused with pseudo-polynomial time, which depends ''linearly'' on the magnitude of values in the problem and is not truly polynomial time.

## Complexity classes

The concept of polynomial time leads to several complexity classes in computational complexity theory. Some important classes defined using polynomial time are the following. * P: The complexity class of
decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...
s that can be solved on a deterministic Turing machine in polynomial time * NP: The complexity class of decision problems that can be solved on a non-deterministic Turing machine in polynomial time * ZPP: The complexity class of decision problems that can be solved with zero error on a
probabilistic Turing machine In theoretical computer science, a probabilistic Turing machine is a non-deterministic Turing machine that chooses between the available transitions at each point according to some probability distribution. As a consequence, a probabilistic Turin ...
in polynomial time * RP: The complexity class of decision problems that can be solved with 1-sided error on a probabilistic Turing machine in polynomial time. * BPP: The complexity class of decision problems that can be solved with 2-sided error on a probabilistic Turing machine in polynomial time *
BQP In computational complexity theory, bounded-error quantum polynomial time (BQP) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.Michael Nielsen and Is ...
: The complexity class of decision problems that can be solved with 2-sided error on a quantum Turing machine in polynomial time P is the smallest time-complexity class on a deterministic machine which is
robust Robustness is the property of being strong and healthy in constitution. When it is transposed into a system, it refers to the ability of tolerating perturbations that might affect the system’s functional body. In the same line ''robustness'' ca ...
in terms of machine model changes. (For example, a change from a single-tape Turing machine to a multi-tape machine can lead to a quadratic speedup, but any algorithm that runs in polynomial time under one model also does so on the other.) Any given
abstract machine An abstract machine is a computer science theoretical model that allows for a detailed and precise analysis of how a computer system functions. It is analogous to a mathematical function in that it receives inputs and produces outputs based on pr ...
will have a complexity class corresponding to the problems which can be solved in polynomial time on that machine.

# Superpolynomial time

An algorithm is defined to take superpolynomial time if ''T''(''n'') is not bounded above by any polynomial. Using little omega notation, it is ''ω''(''n''''c'') time for all constants ''c'', where ''n'' is the input parameter, typically the number of bits in the input. For example, an algorithm that runs for 2''n'' steps on an input of size ''n'' requires superpolynomial time (more specifically, exponential time). An algorithm that uses exponential resources is clearly superpolynomial, but some algorithms are only very weakly superpolynomial. For example, the Adleman–Pomerance–Rumely primality test runs for time on ''n''-bit inputs; this grows faster than any polynomial for large enough ''n'', but the input size must become impractically large before it cannot be dominated by a polynomial with small degree. An algorithm that requires superpolynomial time lies outside the complexity class P. Cobham's thesis posits that these algorithms are impractical, and in many cases they are. Since the P versus NP problem is unresolved, it is unknown whether NP-complete problems require superpolynomial time.

# Quasi-polynomial time

Quasi-polynomial time algorithms are algorithms that run longer than polynomial time, yet not so long as to be exponential time. The worst case running time of a quasi-polynomial time algorithm is $2^$ for some fixed For $c=1$ we get a polynomial time algorithm, for $c < 1$ we get a sub-linear time algorithm. Quasi-polynomial time algorithms typically arise in
reductions Reductions ( es, reducciones, also called ; , pl. ) were settlements created by Spanish rulers and Roman Catholic missionaries in Spanish America and the Spanish East Indies (the Philippines). In Portuguese-speaking Latin America, such re ...
from an
NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
problem to another problem. For example, one can take an instance of an NP hard problem, say
3SAT In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfie ...
, and convert it to an instance of another problem B, but the size of the instance becomes $2^$. In that case, this reduction does not prove that problem B is NP-hard; this reduction only shows that there is no polynomial time algorithm for B unless there is a quasi-polynomial time algorithm for 3SAT (and thus all of NP). Similarly, there are some problems for which we know quasi-polynomial time algorithms, but no polynomial time algorithm is known. Such problems arise in approximation algorithms; a famous example is the directed Steiner tree problem, for which there is a quasi-polynomial time approximation algorithm achieving an approximation factor of $O\left(\log^3 n\right)$ (''n'' being the number of vertices), but showing the existence of such a polynomial time algorithm is an open problem. Other computational problems with quasi-polynomial time solutions but no known polynomial time solution include the planted clique problem in which the goal is to find a large clique in the union of a clique and a
random graph In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs ...
. Although quasi-polynomially solvable, it has been conjectured that the planted clique problem has no polynomial time solution; this planted clique conjecture has been used as a computational hardness assumption to prove the difficulty of several other problems in computational game theory, property testing, and machine learning. The complexity class QP consists of all problems that have quasi-polynomial time algorithms. It can be defined in terms of
DTIME In computational complexity theory, DTIME (or TIME) is the computational resource of computation time for a deterministic Turing machine. It represents the amount of time (or number of computation steps) that a "normal" physical computer would ta ...
as follows. :$\mbox = \bigcup_ \mbox \left\left(2^\right\right)$

## Relation to NP-complete problems

In complexity theory, the unsolved
P versus NP The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved. The informal term ''quickly'', used abov ...
problem asks if all problems in NP have polynomial-time algorithms. All the best-known algorithms for NP-complete problems like 3SAT etc. take exponential time. Indeed, it is conjectured for many natural NP-complete problems that they do not have sub-exponential time algorithms. Here "sub-exponential time" is taken to mean the second definition presented below. (On the other hand, many graph problems represented in the natural way by adjacency matrices are solvable in subexponential time simply because the size of the input is the square of the number of vertices.) This conjecture (for the k-SAT problem) is known as the
exponential time hypothesis In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by . It states that satisfiability of 3-CNF Boolean formulas cannot be solved more quickly than exponential ...
. Since it is conjectured that NP-complete problems do not have quasi-polynomial time algorithms, some inapproximability results in the field of approximation algorithms make the assumption that NP-complete problems do not have quasi-polynomial time algorithms. For example, see the known inapproximability results for the set cover problem.

# Sub-exponential time

The term sub-exponential time is used to express that the running time of some algorithm may grow faster than any polynomial but is still significantly smaller than an exponential. In this sense, problems that have sub-exponential time algorithms are somewhat more tractable than those that only have exponential algorithms. The precise definition of "sub-exponential" is not generally agreed upon, and we list the two most widely used ones below.

## First definition

A problem is said to be sub-exponential time solvable if it can be solved in running times whose logarithms grow smaller than any given polynomial. More precisely, a problem is in sub-exponential time if for every there exists an algorithm which solves the problem in time ''O''(2''n''''ε''). The set of all such problems is the complexity class SUBEXP which can be defined in terms of
DTIME In computational complexity theory, DTIME (or TIME) is the computational resource of computation time for a deterministic Turing machine. It represents the amount of time (or number of computation steps) that a "normal" physical computer would ta ...
as follows. :$\text=\bigcap_ \text\left\left(2^\right\right)$ This notion of sub-exponential is non-uniform in terms of ''ε'' in the sense that ''ε'' is not part of the input and each ε may have its own algorithm for the problem.

## Second definition

Some authors define sub-exponential time as running times in $2^$. This definition allows larger running times than the first definition of sub-exponential time. An example of such a sub-exponential time algorithm is the best-known classical algorithm for integer factorization, the
general number field sieve In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than . Heuristically, its complexity for factoring an integer (consisting of bits) is of the form :\exp\left( ...
, which runs in time about where the length of the input is . Another example was the graph isomorphism problem, which the best known algorithm from 1982 to 2016 solved in However, at STOC 2016 a quasi-polynomial time algorithm was presented. It makes a difference whether the algorithm is allowed to be sub-exponential in the size of the instance, the number of vertices, or the number of edges. In
parameterized complexity In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. ...
, this difference is made explicit by considering pairs $\left(L,k\right)$ of
decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...
s and parameters ''k''. SUBEPT is the class of all parameterized problems that run in time sub-exponential in ''k'' and polynomial in the input size ''n'': :$\text=\text\left\left(2^ \cdot \text\left(n\right)\right\right).$ More precisely, SUBEPT is the class of all parameterized problems $\left(L,k\right)$ for which there is a
computable function Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can d ...
$f : \N \to \N$ with $f \in o\left(k\right)$ and an algorithm that decides ''L'' in time $2^ \cdot \text\left(n\right)$.

### Exponential time hypothesis

The exponential time hypothesis (ETH) is that
3SAT In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfie ...
, the satisfiability problem of Boolean formulas in
conjunctive normal form In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs. As a ...
with at most three literals per clause and with ''n'' variables, cannot be solved in time 2''o''(''n''). More precisely, the hypothesis is that there is some absolute constant such that 3SAT cannot be decided in time 2''cn'' by any deterministic Turing machine. With ''m'' denoting the number of clauses, ETH is equivalent to the hypothesis that ''k''SAT cannot be solved in time 2''o''(''m'') for any integer . The exponential time hypothesis implies P ≠ NP.

# Exponential time

An algorithm is said to be exponential time, if ''T''(''n'') is upper bounded by 2poly(''n''), where poly(''n'') is some polynomial in ''n''. More formally, an algorithm is exponential time if ''T''(''n'') is bounded by ''O''(2''n''''k'') for some constant ''k''. Problems which admit exponential time algorithms on a deterministic Turing machine form the complexity class known as
EXP Exp may stand for: * Exponential function, in mathematics * Expiry date of organic compounds like food or medicines * Experience points, in role-playing games * EXPTIME In computational complexity theory, the complexity class EXPTIME (sometimes ...
. :$\text = \bigcup_ \text\left\left(2^\right\right)$ Sometimes, exponential time is used to refer to algorithms that have ''T''(''n'') = 2''O''(''n''), where the exponent is at most a linear function of ''n''. This gives rise to the complexity class E. :$\text = \bigcup_ \text\left\left(2^\right\right)$

# Factorial time

An algorithm is said to be factorial time if ''T(n)'' is upper bounded by the factorial function ''n!''. Factorial time is a subset of exponential time (EXP) because $n! = O \left\left(2^ \right\right)$ for all $\epsilon > 0$. However, it is not a subset of E. An example of an algorithm that runs in factorial time is
bogosort In computer science, bogosort (also known as permutation sort, stupid sort, slowsort or bozosort) is a sorting algorithm based on the generate and test paradigm. The function successively generates permutations of its input until it finds one t ...
, a notoriously inefficient sorting algorithm based on trial and error. Bogosort sorts a list of ''n'' items by repeatedly
shuffling Shuffling is a procedure used to randomize a deck of playing cards to provide an element of chance in card games. Shuffling is often followed by a cut, to help ensure that the shuffler has not manipulated the outcome. __TOC__ Techniques Over ...
the list until it is found to be sorted. In the average case, each pass through the bogosort algorithm will examine one of the ''n''! orderings of the ''n'' items. If the items are distinct, only one such ordering is sorted. Bogosort shares patrimony with the
infinite monkey theorem The infinite monkey theorem states that a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will almost surely type any given text, such as the complete works of William Shakespeare. In fact, the monkey woul ...
.

# Double exponential time

An algorithm is said to be double exponential time if ''T''(''n'') is upper bounded by 22poly(''n''), where poly(''n'') is some polynomial in ''n''. Such algorithms belong to the complexity class
2-EXPTIME In computational complexity theory, the complexity class 2-EXPTIME (sometimes called 2-EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(22''p''(''n'')) time, where ''p''(''n'') is a polynomial function of '' ...
. :$\mbox = \bigcup_ \mbox\left\left( 2^\right\right)$ Well-known double exponential time algorithms include: * Decision procedures for
Presburger arithmetic Presburger arithmetic is the first-order theory of the natural numbers with addition, named in honor of Mojżesz Presburger, who introduced it in 1929. The signature of Presburger arithmetic contains only the addition operation and equality, omi ...
* Computing a
Gröbner basis In mathematics, and more specifically in computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating set of an ideal in a polynomial ring over a field . A Grö ...
(in the worst case) * Quantifier elimination on real closed fields takes at least double exponential time, and can be done in this time.


text:
#### Vol. 8, No. 2, 2019

 Recent Issues Volume 8, Issue 2 Volume 8, Issue 1
 The Journal About the Journal Subscriptions Editorial Board Submission Guidelines Submission Form Ethics Statement To Appear Editorial Login Contacts ISSN (electronic): 2640-7361 ISSN (print): 2220-5438 founded and published with the scientific support and advice of the Moscow Institute of Physics and Technology Other MSP Journals
On the quotient set of the distance set

### Alex Iosevich, Doowon Koh and Hans Parshall

Vol. 8 (2019), No. 2, 103–115
##### Abstract

Let ${\mathbb{F}}_{q}$ be a finite field of order $q$. We prove that if $d\ge 2$ is even and $E\subset {\mathbb{F}}_{q}^{d}$ with $|E|\ge 9{q}^{d∕2}$ then

${\mathbb{F}}_{q}=\frac{\Delta \left(E\right)}{\Delta \left(E\right)}=\left\{\frac{a}{b}:a\in \Delta \left(E\right),b\in \Delta \left(E\right)\setminus \left\{0\right\}\right\},$

where

$\Delta \left(E\right)=\left\{\parallel x-y\parallel :x,y\in E\right\},\phantom{\rule{1em}{0ex}}\parallel x\parallel ={x}_{1}^{2}+{x}_{2}^{2}+\cdots +{x}_{d}^{2}.$

If the dimension $d$ is odd and $E\subset {\mathbb{F}}_{q}^{d}$ with $|E|\ge 6{q}^{d∕2}$, then

$\left\{0\right\}\cup {\mathbb{F}}_{q}^{+}\subset \frac{\Delta \left(E\right)}{\Delta \left(E\right)},$

where ${\mathbb{F}}_{q}^{+}$ denotes the set of nonzero quadratic residues in ${\mathbb{F}}_{q}$. Both results are, in general, best possible, including the conclusion about the nonzero quadratic residues in odd dimensions.

##### Keywords
quotient set, distance set, finite field
##### Mathematical Subject Classification 2010
Primary: 11T24, 52C17

format: plain


text:
Gregory
3 posts
[Custom Commands] Include Guard + cpp caster
Edited by Gregory on
The code is pretty messy, and I didn't check to see if you already had string operations somewhere else before starting.

Currently guards to throw an error if it finds the file to be included multiple times, can make it do a more traditional guard fairly easy if you would prefer.

Hope someone here has use for it :)

http://i.imgur.com/DpeWLol.gifv

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 void str_cpy(char* dst, const char* src,unsigned len) { for(;len;--len,++src,++dst) *dst = *src; } void replace_chars(char* str, unsigned len, char find, char replace) { for(;len;--len,++str) if(*str == find) *str = replace; } void to_upper(char* str,unsigned len){ for(;len;--len,++str) if(*str >= 0x61 && *str <= 0x7A) *str -= 0x20; } CUSTOM_COMMAND_SIG(include_guard_header){ uint32_t access = AccessOpen; View_Summary view = get_active_view(app, access); Buffer_Summary buffer = get_buffer(app, view.buffer_id, access); char filenamebuf[0x100]; char cbuffer[0x200]; String str = make_fixed_width_string(cbuffer); unsigned len = 0; char* fileshort = buffer.file_name + buffer.file_name_len; for(;*fileshort != '/'; --fileshort, ++len) ; fileshort++; len--; str_cpy(filenamebuf, fileshort, len); replace_chars(filenamebuf, len, ' ', '_'); replace_chars(filenamebuf, len, '.', '_'); to_upper(filenamebuf, len); String fstr = make_string(filenamebuf, len); append(&str, "#ifdef "); append(&str, fstr); append(&str, "\n#error \"File included multiple times.\"\n#endif\n#define "); append(&str, fstr); write_string(app, str); }
Allen Webster
474 posts / 4 projects
Heyo
[Custom Commands] Include Guard + cpp caster
Really nice implementation. I might rip some of this and make an official version of this soon because it's a good feature that a lot of people would probably want. Plus I will be able to make it work through the '4coder_string.h' stuff.

By the way, I normally don't see include guards used to generate errors when a file is included multiple times, but it's interesting. If you don't mind, is there any particular reason you prefer that over the include guard that just prevents the body of the file from being instantiated more than once?
Gregory
3 posts
[Custom Commands] Include Guard + cpp caster
Edited by Gregory on
Its something I have picked up for include files to be aware of looping dependencies, can help compile time (a minuscule amount), but mostly just forces me to not be lazy with including things haha

For files that are just type decls or something i dont mind being everywhere, i just use #pragma once which isnt really in need of a macro imo
Allen Webster
474 posts / 4 projects
Heyo
[Custom Commands] Include Guard + cpp caster
Well I'm thinking about setting up a feature to fill new header files automatically. However having it as a built in command is going to be useful on occasion too.

I'll have to try your include guard system in my next project, it sounds interesting to me.
Gregory
3 posts
[Custom Commands] Include Guard + cpp caster
Edited by Gregory on
Wrote another command to set up the cpp casts for me, going to try to kick the habit of using c casts everywhere.

http://i.imgur.com/XgDy9fm.gifv

in the prompt:

s = static_cast
d = dynamic_cast
c = const_cast
r = reinterpret_cast

Most of it was shamelessly copypasta'd from the #if 0 #endif command.

I was thinking, that for situations where you have T v1 = cast<T>(v2); it could deduce the type you are casting to, curious as to how you would approach that.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 CUSTOM_COMMAND_SIG(write_cpp_cast) { const char sig_static[] = "static_cast<>("; const char sig_dynamic[] = "dynamic_cast<>("; const char sig_const[] = "const_cast<>("; const char sig_reinterpret[] = "reinterpret_cast<>("; const char sig_end[] = ")"; const int sz_static = sizeof(sig_static) - 1; const int sz_dynamic = sizeof(sig_dynamic) - 1; const int sz_const = sizeof(sig_const) - 1; const int sz_reinterpret = sizeof(sig_reinterpret) - 1; const int sz_end = sizeof(sig_end) - 1; char type[8]; const char* cb; int sz; Query_Bar bar; bar.prompt = make_lit_string("Cast type: "); bar.string = make_fixed_width_string(type); if (!query_user_string(app, &bar)) return; end_query_bar(app, &bar, 0); switch(type[0]){ case 's': { cb = sig_static; sz = sz_static; }break; case 'd': { cb = sig_dynamic; sz = sz_dynamic; }break; case 'c': { cb = sig_const; sz = sz_const; }break; case 'r': { cb = sig_reinterpret; sz = sz_reinterpret; }break; default: { return; } } View_Summary view = get_active_view(app, AccessOpen); Buffer_Summary buffer = get_buffer(app, view.buffer_id, AccessOpen); Range range = get_range(&view); if (range.min < range.max){ Buffer_Edit edits[2]; char *str = 0; char *base = (char*)partition_current(&global_part); str = push_array(&global_part, char, sz); memcpy(str, cb, sz); edits[0].str_start = (int32_t)(str - base); edits[0].len = sz; edits[0].start = range.min; edits[0].end = range.min; str = push_array(&global_part, char, sz_end); memcpy(str, sig_end, sz_end); edits[1].str_start = (int32_t)(str - base); edits[1].len = sz_end; edits[1].start = range.max; edits[1].end = range.max; buffer_batch_edit(app, &buffer, base, global_part.pos, edits, ArrayCount(edits), BatchEdit_Normal); if(view.cursor.pos < view.mark.pos){ view_set_cursor(app, &view, seek_line_char(view.cursor.line, view.cursor.character + sz - 2), 1); } else{ view_set_cursor(app, &view, seek_line_char(view.mark.line, view.mark.character + sz - 2), 1); } } }
Allen Webster
474 posts / 4 projects
Heyo
[Custom Commands] Include Guard + cpp caster
Hmm detecting type is going to be a bit of a hack. The best I can think to do is get the index of the first and last characters on the line, which you can do with one of the helpers. Then you can use buffer_get_token_index to find out the range of tokens on the line. Use buffer_read_tokens to get those tokens and then try to parse it and see if it is a variable declaration, but you're on your own for that, and it won't be possible to get it exactly right without the full parse context, but it should be possible to get it right in the cases where you care about it.


text: Virtual Distillation for Quantum Error Mitigation, Focus Beyond Quadratic Speedups for Error-Corrected Quantum Advantage, Even More Efficient Quantum Computations of Chemistry through Tensor Hyper-Contraction, Power of data in quantum machine learning, Optimal fermion-to-qubit mapping via ternary trees with applications to reduced quantum states learning. © The mapping has a simple structure where any single Majorana operator on an n-mode fermionic system is mapped to a multi-qubit Pauli operator acting nontrivially on log_3 (2n+1) qubits. The results announced Wednesday herald the rise of quantum computers. A pair of qubits can store all four combinations simultaneously, because each qubit represents both values (0 and 1) at the same time. Supercomputer lässt er weit hinter sich. Stay up to date on the coronavirus outbreak by signing up to our newsletter today. Damit habe man die Quantum … We introduce a fermion-to-qubit mapping using ternary trees. For example, a pair of bits can store just one of four possible combinations of states (00, 01, 10 or 11) at any given time. 24 October 2019. By This means that measuring the state of one particle allows you to simultaneously know the state of the other, regardless of the distance between the particles. Visit our corporate site. The calculation that Google chose to conquer is the quantum equivalent of generating a very long list of random numbers and checking their values a million times over. This list contains quantum processors, also known as quantum processing units (QPUs). Receive news and offers from our other brands? Here's what happened. Quantum Computing merges two great scientific revolutions of the 20th century: computer science and quantum physics. A 'conceptual' computer that can implement those algorithms is the quantum computer. IBM, Microsoft and Intel are also active in quantum computing. We think quantum computing will help us develop the innovations of tomorrow, including AI. We discuss conditions under which it would be possible for a modest fault-tolerant quantum computer to realize a runtime advantage by executing a quantum algorithm with only a small polynomial speedup over the best classical alternative. Receive mail from us on behalf of our trusted partners or sponsors? Quantencomputer verwenden dagegen so genannte Qubits, die eine Kombination aus Null und Eins gleichzeitig darstellen können, basierend auf einem Prinzip, das als Superposition bezeichnet wird.. Dieser Unterschied verleiht Quantencomputern das Potenzial, … However, a machine learning task where some data is provided can be considerably different than more commonly studied... Hsin-Yuan (Robert) Huang, Michael Blythe Broughton, Masoud Mohseni, Ryan Babbush, Sergio Boixo, Hartmut Neven, Jarrod Ryan McClean. If you add more qubits, your computer's power grows exponentially. Google just took a quantum leap in computer science. Demonstrating the task in the real world is another story. Google’s quantum computer. For certain computations such as optimization, sampling, search or quantum simulation this promises dramatic speedups. Google's Sycamore chip is kept cool inside their quantum cryostat. Americans celebrated Thanksgiving during a pandemic before. Whereas classical computers can stack millions of operating bits in their processors, quantum computers struggle to scale the number of qubits they can operate with. Related: The 11 Most Beautiful Mathematical Equations. But on the algorithmic level, today's computing machinery still operates on ""classical"" Boolean logic. Using the company's state-of-the-art quantum computer, called Sycamore, Google has claimed "quantum supremacy" over the … Ordinary computers perform calculations using "bits" of information, which, like on-and-off switches, can exist in only two states: either 1 or 0. Quantum computers use quantum bits, or "qubits," which can exist as both 1 and 0 simultaneously. Google says it achieved quantum supremacy with a computer that is far faster than supercomputers. This number gets even more impressive when another fundamental and equally bizarre property of quantum mechanics enters the show: entangled states. "But since we are currently 1.5 trillion times faster, we feel comfortable laying claim to this achievement," he added, referring to the supremacy of quantum computers. We describe quantum circuits with only $\widetilde{\cal O}(N)$ Toffoli complexity that block encode the spectra of quantum chemistry Hamiltonians in a basis of $N$ arbitrary (e.g., molecular) orbitals. The use of quantum computing for machine learning is among the most exciting prospective applications of quantum technologies. Klassische Computer werden mit Bits als Dateneinheiten (Nullen und Einsen) programmiert. Related: 18 Times Quantum Physics Blew Our Minds. They have also said this milestone puts a … The largest quantum computer to date is Google’s 72-qubit processor called Bristlecone, and that hasn’t even demonstrated quantum supremacy. The quantum computer completed the complex computation in 200 seconds. This is the largest chemical simulation performed on quantum computer to date reported Google. Quantum physics is the theoretical basis of the transistor, the laser, and other technologies which enabled the computing revolution. The challenge is that the computation must finish within a reasonable amount of time while being difficult enough that the small quantum scaling advantage... Ryan Babbush, Jarrod Ryan McClean, Craig Michael Gidney, Sergio Boixo, Hartmut Neven. Using the company's state-of-the-art quantum computer, called Sycamore, Google has claimed "quantum supremacy" over the most powerful supercomputers in the world by solving a problem considered virtually impossible for normal machines. If the qubits of a quantum computer are entangled, they can all be measured simultaneously. The result is a solution not particularly useful outside of the world of quantum mechanics, but it has big implications for the processing power of a device. Google has described the recent achievement as a "milestone towards full-scale quantum computing." : I-5.. Google's first steps. New York, You will receive a verification email shortly. Google has its own plan to build a million-qubit quantum computer within 10 years, as Hartmut Neven, who leads Google’s quantum computing … That same calculation would take even the most powerful supercomputers approximately 10,000 years to finish, the team of researchers, led by John Martinis, an experimental physicist at the University of California, Santa Barbara, wrote in their study published Wednesday (Oct. 23) in the journal Nature. Quantum Computing - Funktionsweise. Auch wenn er zunächst nur eine nutzlose Aufgabe gelöst hat.


text:
### 纳米材料在生物分析应用中存在的若干问题

1. a 中国科学院化学研究所 活体分析化学重点实验室 北京 100190;
b 北京大学第三医院耳鼻咽喉科 北京 100191
• 投稿日期:2013-08-29 发布日期:2013-09-10
• 通讯作者: 刘俊秀, 马会民 E-mail:liujunxiusanyuan@sina.com;mahm@iccas.ac.cn
• 基金资助:

项目受国家自然科学基金（No. 21321003）、973计划（2011CB935800，2010CB933502）和中国科学院资助.

### Some Problems of Nanomaterials in Bioanalytical Applications

Song Yanchaoa, Liu Junxiub, Zhang Yangyanga, Shi Wena, Ma Huimina

1. a Beijing National Laboratory for Molecular Sciences, Key Laboratory of Analytical Chemistry for Living Biosystems, Institute of Chemistry, Chinese Academy of Sciences, Beijing 100190;
b Department of Otorhinolaryngology, Peking University Third Hospital, Beijing 100191
• Received:2013-08-29 Published:2013-09-10
• Supported by:

Project supported by the National Natural Science Foundation of China (No. 21321003), the 973 Program (2011CB935800, and 2010CB933502) and the Chinese Academy of Sciences.

By taking the three commonly used CdTe quantum dots (CdTe QDs), Au nanoparticles (Au NPs) and carbon nanodots (C-dots) as example, we have demonstrated and summarized some noteworthy problems of nanomaterials in bioanalytical applications. These problems mainly include the toxicity, microscopic heterogeneity and environmental susceptivity of nanomaterials, which had been separately discussed with different depths but unfortunately are often overlooked in practice. In the present work, a parallel comparative investigation was first made on cytotoxicity, which reveals that CdTe QDs can lead to the decrease of cell metabolic activity, cell shrinkage, and even cell death; Au NPs at a higher concentration (30 μg/mL) decrease the metabolic activity of cells to a small extent; C-dots exert no obvious toxicity to live cells, showing good biocompatibility. These studies indicate that the relative toxicity of the three nanomaterials in their bare forms is CdTe QDs>>AuNPs>C-dots, which is further supported by the inhibition experiment on the growth of green gram sprouts. Second, the microscopic heterogeneity of nanomaterials was compared with that of resorufin (a small molecular fluorescent dye) by cell imaging experiments, which clearly shows that the distribution of nanomaterials in cells is much less uniform than that of small molecular probes. Besides, the heterogeneity of both size distribution and surface modification/property of nanomaterials is also unavoidable. Third, the environmental susceptivity of nanomaterials was studied, and the results showed that spectroscopic properties of the above three nanomaterials are all sensitive to the pH change of solution. Moreover, AuNPs are also rather susceptible to the ionic strength of solution. The above three problems should arouse high attention of researchers in some bioanalyses. In addition, the measures that we suggested in the paper may be helpful to solve these problems to some extent.


text:
# Mach wave

Schlieren photograph of an attached shock on a sharp-nosed supersonic body. The Mach angle is acute, showing that the body exceeds Mach 1.

In fluid dynamics, a Mach wave is a pressure wave traveling with the speed of sound caused by a slight change of pressure added to a compressible flow. These weak waves can combine in supersonic flow to become a shock wave if sufficient Mach waves are present at any location. Such a shock wave is called a Mach stem or Mach front. Thus it is possible to have shockless compression or expansion in a supersonic flow by having the production of Mach waves sufficiently spaced (cf. isentropic compression in supersonic flows). A Mach wave is the weak limit of an oblique shock wave (a normal shock is the other limit). They propagate across the flow at the Mach angle μ:[1]

$\mu = \arcsin\left(\frac{1}{M}\right),$

where M is the Mach number.

Mach waves can be used in schlieren or shadowgraph observations to determine the local Mach number of the flow. Early observations by Ernst Mach used grooves in the wall of a duct to produce Mach waves in a duct, which were then photographed by the schlieren method, to obtain data about the flow in nozzles and ducts. Mach angles may also occasionally be visualized out of their condensation in air, as in the jet photograph below.

U.S. Navy F/A-18 at transonic speed. The white halo is formed by condensed water droplets which are thought to result from an increase in air temperature and pressure behind the shockwave(see Prandtl-Glauert Singularity). The Mach angle of the weak attached shock made visible by the halo is seen to be close to arcsin (1) = 90 degrees.[2][3]


text:
# Category:Semigroup Homomorphisms

This category contains results about Semigroup Homomorphisms.
Definitions specific to this category can be found in Definitions/Semigroup Homomorphisms.

Let $\left({S, \circ}\right)$ and $\left({T, *}\right)$ be semigroups.

Let $\phi: S \to T$ be a mapping such that $\circ$ has the morphism property under $\phi$.

That is, $\forall a, b \in S$:

$\phi \left({a \circ b}\right) = \phi \left({a}\right) * \phi \left({b}\right)$

Then $\phi: \left({S, \circ}\right) \to \left({T, *}\right)$ is a semigroup homomorphism.

## Subcategories

This category has only the following subcategory.

## Pages in category "Semigroup Homomorphisms"

This category contains only the following page.


text:
# Divergent series for $\displaystyle\sum_{n=0}^\infty z^{n!}$

I have calculated using the root test that the radius of convergence of $\displaystyle\sum_{n=0}^\infty z^{n!}$ is $1$.

But how would I show that there is an infinite number of $z \in \mathbb{C}$ with $|z|=1$ for which the series diverge? I don't really understand what is meant in the above question, could someone explain to me what the question means?

-
The more interesting question is what might happen as you move out, within the unit disk, towards a point on the boundary, and evaluate the function on such points. – Lubin May 26 '12 at 0:25
Thanks Lubin, I'm currently thinking over this question, hope to make some progress soon. – Derrick May 26 '12 at 0:46
This is a lacunary function: en.wikipedia.org/wiki/Lacunary_function – deoxygerbe May 26 '12 at 5:09

Terms not going to zero implies series not converging.

-

You have already found out that the radius of convergence is $1$. This means that for $z$ with $|z|<1$, the series converges and for $|z|>1$, the series diverges. On the radius of convergence itself, i.e. for $|z|=1$, pretty much anything can happen.

Note that the set $\{z\in \mathbb{C}:|z|=1\}$ is a circle around $(0,0)$ with radius one. You have to prove that the series diverges for infinitely many points on the circle. One example of such a point is $z=1$, but apparently there are infinitely many more. One possible way (but not necessarily the correct way) is to show that there are only finitely, or countably, many points on the circle for which the series does converge.

-
Actually convergence is impossible on the boundary, for the reason Gerry states (at least for this particular series - I understand nothing so strong can be said in the general case scenario). Perhaps there are points where the partial sums are bounded, though. (If there was a monotonic decreasing coefficient present like $n^{-1/2}$ or whatever, I would point out roots of unity as an infinite number of cases where the series diverges.) – anon May 26 '12 at 0:35
But didn't he just ask for the meaning of the question? AS I understood it, that as the most important part of his question – Egbert May 26 '12 at 0:42
It wasn't specified in the first few sentences that the general case was being discussed, rather than this particular case, so I wanted to clear up ambiguity just in case it were to be an issue. – anon May 26 '12 at 0:49

As the comment pointed out this is a lacunary series,there is corresponding criterion for such seriesOstrowski-Hadamard gap theroem

-


text:
# When does Schwarz inequality become an equality?

In Spivak Calculus you are asked to prove that in Schwarz inequality, equality holds only when $y_1 = y_2 = 0$ or when there is a number $\lambda$ such that $x_1 = \lambda y_1$ and $x_2 = \lambda y_2$.

I can go from $x_1y_1 + x_2y_2 = \sqrt{x_1^2 + x_2^2} + \sqrt{y_1^2 + y_2^2}$ to $x_1y_2 = x_2y_1$ but then I got stuck, or is it that the implication is the other way around?

• That's correct. Conclude that if neither of $y_1, y_2$ are 0, then $\frac {x_1}{y_1} = \frac {x_2}{y_2}$, and set it to be your favorite parameter. Then deal with the case $y_1 y_2 = 0$. – Calvin Lin Jan 15 '13 at 4:28
• Thank you Calvin, with your $\lambda = \frac{x_1}{y_1}$ trick I was able to complete the proof. – Édgar Sánchez Gordón Jan 15 '13 at 5:23
• $x_1,\,x_2,\,y_1,\,y_2,\lambda \in \mathbb{R}$? – scjorge Jun 7 '16 at 3:41
• @scjorge Yep, all real numbers. – Édgar Sánchez Gordón Dec 6 '17 at 16:58

$|\langle \mathbf{x},\mathbf{y}\rangle|=\|\mathbf{x}\|\,\|\mathbf{y}\| \iff \mathbf{x}$ and $\mathbf{y}$ are linearly dependent, i.e. if $\mathbf{x}=\lambda\mathbf{y}$ (or, trivially, if either $\mathbf{x}$ or $\mathbf{y}$ is zero; handle this first to get it out of the way).
($\implies$): Follow the normal Schwarz inequality argument, but equality will force $\mathbf{x}={\langle \mathbf{x},\mathbf{y}\rangle\over \langle\mathbf{y},\mathbf{y}\rangle}\mathbf{y}$
($\Longleftarrow$): Substitute $\mathbf{x}=\lambda\mathbf{y}$.
Since $$\left(x_1^2+x_2^2\right)\left(y_1^2+y_2^2\right)-(x_1y_1+x_2y_2)^2=(x_1y_2-x_2y_1)^2$$ we get equality if and only if $x_1y_2=x_2y_1$.


text:
# Deal Damage to Player

I have to make a simple "avalanche" game to show I know how to use the physics and creating terrain. But I actually wanted to go a little above and beyond and actually give the player health so there is a actual purpose to dodging the sphere objects. I found a very useful guide on how to set up player health, the only thing is I don't know how to set up the player taking damage when he collides with a sphere. Here is the code I have for the players health

#pragma strict

public var health : float = 100f;                           // How much health the player has left.
public var resetAfterDeathTime : float = 5f;                // How much time from the player dying to the level reseting.
public var deathClip : AudioClip;                           // The sound effect of the player dying.

private var anim : Animator;                                // Reference to the animator component.
private var playerMovement : PlayerMovement;            // Reference to the player movement script.
private var hash : HashIDs;                             // Reference to the HashIDs.
private var lastPlayerSighting : LastPlayerSighting;    // Reference to the LastPlayerSighting script.
private var timer : float;                                  // A timer for counting to the reset of the level once the player is dead.
private var playerDead : boolean;                           // A bool to show if the player is dead or not.

function Awake ()
{
// Setting up the references.
anim = GetComponent(Animator);
playerMovement = GetComponent(PlayerMovement);
hash = GameObject.FindGameObjectWithTag(Tags.gameController).GetComponent(HashIDs);
lastPlayerSighting = GameObject.FindGameObjectWithTag(Tags.gameController).GetComponent(LastPlayerSighting);
}

function Update ()
{
// If health is less than or equal to 0...
if(health <= 0f)
{
// ... and if the player is not yet dead...
// ... call the PlayerDying function.
PlayerDying();
else
{
// Otherwise, if the player is dead, call the PlayerDead and LevelReset functions.
LevelReset();
}
}
}

function PlayerDying ()
{
// The player is now dead.

// Set the animator's dead parameter to true also.

// Play the dying sound effect at the player's location.
AudioSource.PlayClipAtPoint(deathClip, transform.position);
}

{
// If the player is in the dying state then reset the dead parameter.
if(anim.GetCurrentAnimatorStateInfo(0).nameHash == hash.dyingState)

// Disable the movement.
anim.SetFloat(hash.speedFloat, 0f);
playerMovement.enabled = false;

// Reset the player sighting to turn off the alarms.
lastPlayerSighting.position = lastPlayerSighting.resetPosition;

// Stop the footsteps playing.
audio.Stop();
}

function LevelReset ()
{
// Increment the timer.
timer += Time.deltaTime;

//If the timer is greater than or equal to the time before the level resets...
if(timer >= resetAfterDeathTime)
// ... reset the level.
}

public function TakeDamage (amount : float)
{
// Decrement the player's health by amount.
health -= amount;
}

Thanks for the help guys, and helping me to learn unity.

First off, if you are that new to Unity, maybe you would benefit a lot from going through tutorials. Unity website has some pretty handy tutorials, plus some nice step-by-step complete projects.

Nevertheless I´m going to give you a general answer to guide you with your question. For my answer I assume you are familiar with some basic Unity3D concepts, as you point out, in order to avoid overexplaining every little detail.

I guess the balls you mention have a Rigidbody in order to be affected by physics. These Rigidbody have a function called OnCollisionEnter, that is called when the Rigidbody hits another Rigidbody/Collider. If your players doesn´t have one of those, you will need to add a Collider in order to allow it to interact with the balls. CapsuleCollider is used usually for players.

Once you have both objects with a Rigidbody/Collider, you can write the OnCollisionEnter function on the ball. Notice that OnCollisionEnter takes as a parameter a Collision, which has a parameter that is the gameObject the ball has collided with. Then you will need to make sure that it is the player, and then call the TakeDamage function.

I hope that helps.

Check out colliders. You'd likely want to implement OnCollisionEnter in your character class. When something collides with the player, this method will be activated. Inside this method is where you'll deduct from the player's health.

If the player can only collide with one thing (the sphere objects), you can make it pretty simple:

function OnCollisionEnter(collision : Collision) {
TakeDamage(5);
}

Read up on what's required for the OnCollisionEnter method to be called, to ensure you have your scene set up correctly (i.e. colliders attached and rigid bodies where needed).


text:
# Approximation Numbers of Composition Operators on Weighted Hardy Spaces

Authors

1 School of Mathematics, Shri Mata Vaishno Devi University, Kakryal, Katra- 182320, J& K, India.

2 Ambika Bhat, School of Mathematics, Shri Mata Vaishno Devi University, Kakryal, Katra-182320, J& K, India.

Abstract

In this paper we find upper and lower bounds for approximation numbers of compact composition operators on the weighted Hardy spaces Hσ under some conditions on the weight function σ:

Keywords

Main Subjects