Javascript must be enabled to continue!

# “Helping”: several formalizations

View through CrossRef

Much recent work in the theory of computational complexity ([Me], [FR]. [SI]) is concerned with establishing “the complexity” of various recursive functions, as measured by the time or space requirements of Turing machines which compute them. In the above work, we also observe another phenomenon: knowing the values of certain functions makes certain other functions easier to compute than they would be without this knowledge. We could say that the auxiliary functions “help” the computation of the other functions.For example, we may conjecture that the “polynomial-complete” problems of Cook [C] and Karp [K] and Stockmeyer [S2], such as satisfiability of propositional formulas or 3-colorability of planar graphs, in fact require time proportional to nlog2n to be computed on a deterministic Turing machine. Then since the time required to decide if a planar graph with n nodes is 3-colorable can be lowered to a polynomial in n if we have a precomputed table of the satisfiable formulas in the propositional calculus, it is natural to say that the satisfiability problem “helps” the computation of the answers to the 3-coloring problem. Similar remarks may be made for any pair of polynomial-complete problems.As a further illustration, Meyer and Stockmeyer [MS] have shown that, for a certain alphabet Σ, recognition of the set of regular expressions with squaring which are equivalent to Σ* requires Turing machine space cn for some constant c, on an infinite set of arguments. We also know that this set of regular expressions, which we call RSQ, may actually be recognized in space dn for some other constant d. Theorem 6.2 in [LMF] implies that there is some problem (not necessarily an interesting one) of complexity approximately equal to that of RSQ, which does not reduce the complexity of RSQ below cn. It does not “help” the computation of RSQ.

Title: “Helping”: several formalizations

Description:

Much recent work in the theory of computational complexity ([Me], [FR].

[SI]) is concerned with establishing “the complexity” of various recursive functions, as measured by the time or space requirements of Turing machines which compute them.

In the above work, we also observe another phenomenon: knowing the values of certain functions makes certain other functions easier to compute than they would be without this knowledge.

We could say that the auxiliary functions “help” the computation of the other functions.

For example, we may conjecture that the “polynomial-complete” problems of Cook [C] and Karp [K] and Stockmeyer [S2], such as satisfiability of propositional formulas or 3-colorability of planar graphs, in fact require time proportional to nlog2n to be computed on a deterministic Turing machine.

Then since the time required to decide if a planar graph with n nodes is 3-colorable can be lowered to a polynomial in n if we have a precomputed table of the satisfiable formulas in the propositional calculus, it is natural to say that the satisfiability problem “helps” the computation of the answers to the 3-coloring problem.

Similar remarks may be made for any pair of polynomial-complete problems.

As a further illustration, Meyer and Stockmeyer [MS] have shown that, for a certain alphabet Σ, recognition of the set of regular expressions with squaring which are equivalent to Σ* requires Turing machine space cn for some constant c, on an infinite set of arguments.

We also know that this set of regular expressions, which we call RSQ, may actually be recognized in space dn for some other constant d.

Theorem 6.

2 in [LMF] implies that there is some problem (not necessarily an interesting one) of complexity approximately equal to that of RSQ, which does not reduce the complexity of RSQ below cn.

It does not “help” the computation of RSQ.

## Related Results

Between elderly parents and adult children: a new look at the intergenerational care provided by the ‘sandwich generation’

Between elderly parents and adult children: a new look at the intergenerational care provided by the ‘sandwich generation’

The ‘sandwich generation’ has been conceptualised as those mid-life adults who simultaneously raise dependent children and care for frail elderly parents. Such a combination of dep...

USE-ALTERATION ANALYSIS OF FIRE-CRACKED ROCKS

USE-ALTERATION ANALYSIS OF FIRE-CRACKED ROCKS

Although it is now commonplace for archaeologists to study use-alteration patterns on ceramics, the same cannot be said of one of the most ubiquitous classes of hunter-gatherer art...

Organizational Citizenship: A Review, Proposed Model, and Research Agenda

Organizational Citizenship: A Review, Proposed Model, and Research Agenda

Organizational citizenship was recently proposed as a form of job performance which may be more strongly related to job satisfaction than performance measures employed in previous ...

Singapore as non-place: National cinema through the lens of temporal heterogeneity

Singapore as non-place: National cinema through the lens of temporal heterogeneity

This article suggests that Singapore and Singapore cinema serve as a good site to return to debates surrounding the national. First, I investigate the disconnect between the presen...

“In search of our better selves”: Totem Transfer Narratives and Indigenous Futurities

“In search of our better selves”: Totem Transfer Narratives and Indigenous Futurities

Much contemporary science fiction urges us to focus on eco-activism and sustainable futures in order to prevent environmental catastrophe. From a critical Indigenous and anticoloni...

Texture in Okigbo’s poetry: An exploration of cohesion

Texture in Okigbo’s poetry: An exploration of cohesion

Even among system texts, poetic language is unique. On the surface, the words appear disparate, resulting in the perceived difficulty associated with its study/analysis. Okigbo’s w...

Storying community: Re-imagining regional identities through public cultural activity

Storying community: Re-imagining regional identities through public cultural activity

This article is designed to stimulate discussion around a number of related topics. Sceptical that governments, regional or otherwise, are capable of producing regional identities ...

Vauxhall on the boulevard: pleasure gardens in London and Paris, 1764–1784

Vauxhall on the boulevard: pleasure gardens in London and Paris, 1764–1784

ABSTRACT:Open to both aristocracy and middling rank, pleasure gardens fashioned a spectacle of order out of a heterogeneous crowd. They have been seen as uniquely British spaces, d...