CushionTheBlow (구 BluemoonSoft)

In computational complexity theory the Blum axioms or Blum complexity axioms are axioms which specify desirable properties of complexity measures on the set of computable functions. The axioms were first defined by Manuel Blum in 1967.

Importantly, the Speedup and Gap theorems hold for any complexity measure satisfying these axioms. The most well-known measures satisfying these axioms are those of time (i.e., running time) and space (i.e., memory usage).

Reference:
http://en.wikipedia.org/wiki/Blum_axioms

In formal language theory, a branch of mathematics used in both computer science and linguistics, a grammar is a precise description of a language – that is, of a set of strings over some alphabet. In other words, a grammar describes which of the possible sequences of symbols (strings) in a language actually constitute valid words or statements in that language, but it does not describe their semantics (i.e. what they mean).

A grammar is usually regarded as a means to generate all the valid strings of a language; it can also be used as the basis for a recognizer that determines for any given string whether it is grammatical (i.e. belongs to the language). To describe such recognizers, formal language theory uses separate formalisms, known as automata.

A grammar can also be used to analyze the strings of a language – i.e. to describe their internal structure. In computer science, this process is known as parsing. Most languages have very compositional semantics, i.e. the meaning of their utterances is structured according to their syntax; therefore, the first step to describing the meaning of an utterance in language is to analyze it and look at its analyzed form (known as its parse tree in computer science, and as its deep structure in generative grammar).

Reference:
http://en.wikipedia.org/wiki/Formation_rules

In mathematical logic, a well-formed formula (often abbreviated WFF, pronounced "wiff") is a symbol or string of symbols (a formula) that is generated by the formal grammar of a formal language. To say that a string S is a WFF with respect to a given formal grammar G is equivalent to saying that S belongs to the language generated by G, i.e. S ∈ L(G). A formal language can be identified with the set of its WFFs.

In formal logic, proofs are sequences of WFFs with certain properties, and the final WFF in the sequence is what is proven. This final WFF is called a theorem when it plays a significant role in the theory being developed, or a lemma when it plays an accessory role in the proof of a theorem.

Reference:
http://en.wikipedia.org/wiki/Well-formed_formula

NP-hard (nondeterministic polynomial-time hard), in computational complexity theory, is a class of problems informally "at least as hard as the hardest problems in NP." A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H, i.e. L <= T_H. In other words, L can be solved in polynomial time by an oracle machine with an oracle for H. Informally we can think of an algorithm that can call such an oracle machine as subroutine for solving H, and solves L in polynomial time if the subroutine call takes only one step to compute. NP-hard problems may be of any type: decision problems, search problems, optimization problems.

As consequences of such definition, we have (note that these are claims, not definitions):

problem H is at least as hard as L, because H can be used to solve L;
since L is NP-complete, and hence the hardest in class NP, also problem H is at least as hard as NP, but H does not have to be in NP and hence does not have to be a decision problem;
since NP-complete problems transform to each other by polynomial-time many-one reduction (also called polynomial transformation), therefore all NP-complete problems can be solved in polynomial time by a reduction to H, thus all problems in NP reduce to H; note however, that this involves combining two different transformations: from NP-complete decision problems to NP-complete problem L by polynomial transformation, and from L to H by polynomial Turing reduction;
if there is a polynomial algorithm for any NP-hard problem, then there are polynomial algorithms for all problems in NP, and hence P = NP;
if P != NP, then NP-hard problems have no solutions in polynomial time, while P = NP does not resolve whether the NP-hard problems can be solved in polynomial time;
if an optimization problem H has an NP-complete decision version L, then H is NP-hard;
if H is in NP, then H is also NP-complete because in this case the existing polynomial Turing transformation fulfills the requirements of polynomial time transformation.
A common mistake is to think that the "NP" in "NP-hard" stands for "non-polynomial". Although it is widely suspected that there are no polynomial-time algorithms for these problems, this has never been proven.

Reference:
http://en.wikipedia.org/wiki/Np_hard

First-order logic (FOL) is a formal deductive system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus (FOPC), the lower predicate calculus, the language of first-order logic or predicate logic. Unlike natural languages such as English, FOL uses a wholly unambiguous formal language interpreted by mathematical structures. FOL is a system of deduction extending propositional logic by allowing quantification over individuals of a given domain of discourse. For example, it can be stated in FOL "Every individual has the property P".

While propositional logic deals with simple declarative propositions, first-order logic additionally covers predicates and quantification. Take for example the following sentences: "Socrates is a man", "Plato is a man". In propositional logic these will be two unrelated propositions, denoted for example by p and q. In first-order logic however, both sentences would be connected by the same property: Man(x), where Man(x) means that x is a man. When x=Socrates we get the first proposition, p, and when x=Plato we get the second proposition, q. Such a construction allows for a much more powerful logic when quantifiers are introduced, such as "for every x...", for example, "for every x, if Man(x), then...". Without quantifiers, every valid argument in FOL is valid in propositional logic, and vice versa.

A first-order theory consists of a set of axioms (usually finite or recursively enumerable) and the statements deducible from them given the underlying deducibility relation. Usually what is meant by 'first-order theory' is some set of axioms together with those of a complete (and sound) axiomatization of first-order logic, closed under the rules of FOL. (Any such system FOL will give rise to the same abstract deducibility relation, so we needn't have a fixed axiomatic system in mind.) A first-order language has sufficient expressive power to formalize two important mathematical theories: ZFC set theory and Peano arithmetic. A first-order language cannot, however, categorically express the notion of countability even though it is expressible in the first-order theory ZFC under the intended interpretation of the symbolism of ZFC. Such ideas can be expressed categorically with second-order logic.

Reference:
http://en.wikipedia.org/wiki/First_order_logic

In logic and mathematics, a propositional calculus (or a sentential calculus) is a formal system in which formulae representing propositions can be formed by combining atomic propositions using logical connectives, and a system of formal proof rules allows certain formulæ to be established as "theorems".

Reference:
http://en.wikipedia.org/wiki/Propositional_logic

The Riemann hypothesis (also called the Riemann zeta-hypothesis), first formulated by Bernhard Riemann in 1859, is one of the most famous and important unsolved problems in mathematics. It has been an open question for almost 150 years, despite attracting concentrated efforts from many outstanding mathematicians. Unlike some other celebrated problems, it is more attractive to professionals in the field than to amateurs.

The Riemann hypothesis (RH) is a conjecture about the distribution of the zeros of the Riemann zeta-function ζ(s). The Riemann zeta-function is defined for all complex numbers s ≠ 1. It has zeros at the negative even integers (i.e. at s = −2, s = −4, s = −6, ...). These are called the trivial zeros. The Riemann hypothesis is concerned with the non-trivial zeros, and states that:

The real part of any non-trivial zero of the Riemann zeta function is ½.
Thus the non-trivial zeros should lie on the so-called critical line, ½ + it, where t is a real number and i is the imaginary unit. The Riemann zeta-function along the critical line is sometimes studied in terms of the Z-function, whose real zeros correspond to the zeros of the zeta-function on the critical line.

The Riemann hypothesis is one of the most important open problems of contemporary mathematics, mainly because a large number of deep and important other results have been proven under the condition that it holds. Most mathematicians believe the Riemann hypothesis to be true. (J. E. Littlewood and Atle Selberg have been reported as skeptical. Selberg's skepticism, if any, waned from his young days. In a 1989 paper, he suggested that an analogue should hold for a much wider class of functions, the Selberg class.) A $1,000,000 prize has been offered by the Clay Mathematics Institute for the first correct proof.

Reference:
http://en.wikipedia.org/wiki/Riemann_hypothesis