Advice (complexity)

In computational complexity theory, an advice string is an extra input to a Turing machine that is allowed to depend on the length n of the input, but not on the input itself. A decision problem is in the complexity class P/f(n) if there is a polynomial time Turing machine M with the following property: for any n, there is an advice string A of length f(n) such that, for any input x of length n, the machine M correctly decides the problem on the input x, given x and A.

The most common complexity class involving advice is P/poly where advice length f(n) can be any polynomial in n. P/poly is equal to the class of decision problems such that, for every n, there exists a polynomial size Boolean circuit correctly deciding the problem on all inputs of length n. One direction of the equivalence is easy to see. If, for every n, there is a polynomial size Boolean circuit A(n) deciding the problem, we can use a Turing machine that interprets the advice string as a description of the circuit. Then, given the description of A(n) as the advice, the machine will correctly decide the problem on all inputs of length n. The other direction uses a simulation of a polynomial-time Turing machine by a polynomial-size circuit as in one proof of Cook's Theorem. Simulating a Turing machine with advice is no more complicated than simulating an ordinary machine, since the advice string can be incorporated into the circuit.

Advice

Advice (noun) or advise (verb) may refer to:

Advice (constitutional)

Advice, in constitutional law, is formal, usually binding, instruction given by one constitutional officer of state to another. Especially in parliamentary systems of government, heads of state often act on the basis of advice issued by prime ministers or other government ministers. For example, in constitutional monarchies, the monarch usually appoints Ministers of the Crown on the advice of his or her prime minister.

Among the most prominent forms of advice offered are:

In some states, the duty to accept advice is legally enforceable, having been created by a constitution or statute. For example, the Basic Law of Germany requires the President to appoint federal ministers on the advice of the Chancellor. In others, especially under the Westminster system, advice may legally be rejected; for example, in several Commonwealth realms, the Queen is not legally obliged to accept the advice of her ministers. This lack of obligation forms part of the basis for the Queen's reserve powers. Nevertheless, the convention that the head of state accept ministerial advice is so strong that in ordinary circumstances, refusal to do so would almost certainly provoke a constitutional crisis.

Advice (programming)

In aspect and functional programming, advice describes a class of functions which modify other functions when the latter are run; it is a certain function, method or procedure that is to be applied at a given join point of a program.

The following is taken from a discussion at the mailing list aosd-discuss. Pascal Costanza contributed the following:

The term advice goes back to the term advising as introduced by Warren Teitelman in his PhD thesis in 1966. Here is a quote from Chapter 3 of his thesis:

"Advising" found its way into BBN Lisp and later into Xerox PARC's Interlisp.

It also found its way to Flavors, the first object-oriented extension to Lisp developed at MIT. They were subsumed under the notion of method combination. See, for example, AIM-602 at http://www.ai.mit.edu/research/publications/browse/0600browse.shtml ¹

Since method combination and macros are closely related, it's also interesting to note that the first macro system was described in 1963, three years before Warren Teitelman's PhD thesis. See AIM-57 at http://www.ai.mit.edu/research/publications/browse/0000browse.shtml ²