Re: Turing machines and partially specified input strings

Now, my boss (I'm a java programmer :-) can ask me ... "well done
Marzio, but where the hell is the Hamiltonian circuit?"

The complexity class NP is a set of decision problems. Each of them has
the form "Is the input string in this language?", and a decider just has
to accept or reject. An HC decider does not need to find the Hamiltonian
circuit, just find out whether the graph contains one.
The oracle would either indicate that the input is not in
HCparity, or supply the circuit. The length of the result would still be
bounded by a polynomial in the length of the original input.

I agree with you - this is "pure" complexity theory, - and you're
right.

But I found nowhere (but - again - my knowledge on the subject is very
limited) a discussion about the "differences" between the two
problems:

1) "find if an Hamiltonian circuit in a given graph exists" (i.e.
output 0 or 1)

2) "find at lest one *real* Hamiltonian circuit in a given graph if it
exists" (i.e. output the circuit)

The two tasks are very different in the real world.

I think that (is this philosophy?), in the "arithmetic world" the two
problems can be faced separately, but when we switch to "Turing
Machine world" our mind cannot think of 1 without passing from 2

Is there in complexity theory problems for which the two tasks are
different in time complexity?



- we can set that the oracle is feeded with a missing node of the
graph
- ..... or a missing edge
... and investigate how this impacts on the efficiency of the whole TM

**** I'm not sure I see the point of doing that. ****

This is my original question for which I asked if some papers exists
out there! :-D

Looking at your example, perhaps the useness is to classify/identify
the "role" of each part of the input ?!?!?

In concrete, I'm wondering if a PIN-ORACLE can make an HC problem
easier if it is feeded with the input graph without a node (and its
associated edges).

best regards,
Marzio


P.S. my _refined_ foolish conjecture (that will last until the next
Patricia reply) :-D :-D

*** P != NP iif exists f in NP but no XTM exists that can
compute f in O(n^k) whatever PIN-ORACLE is choosen ***




.

Relevant Pages

  • Re: number combinations of components
    ... >>>yeah, if one considers them distinct it would be 8. ... The background for this is graph theory, where a graph G consists of a ... but there are many cases where the phase will produce a circuit that ... > I want all the ways to compose these functions. ...
    (sci.math)
  • Re: Complexity of Discrete Log Algorithms
    ... [though really they never specify hardware gates]. ... is some circuit of if/then/else statements which evaluate your problem. ... a linear number of gates have stabalized. ... complexity of n additions which is O. ...
    (sci.crypt)
  • Re: Maintaining a Vbe Multipliers bias value
    ... EDN about a self biasing preamp which was kinda cool. ... ...Jim Thompson ... of the circuit is to minimize the voltage difference between the two inputs. ... the bias current needs (top graph) at the _circuit_ input... ...
    (sci.electronics.design)
  • Re: Tuned Preselectors - Looking for info
    ... diodes tendancy for IMD on strong signals. ... complexity of the circuit. ...
    (rec.radio.amateur.homebrew)
  • Re: Adjustable voltage source from 0 to 12V
    ... Using a LM317, I can create an adjustable voltage supply without much complexity, but it cannot go lower than 1.25V ... I'd like to see your favorite circuit for this. ... Short circuit, open circuit, drive output positive, drive output negative, load dump, input voltage dump, transient response...the usual stuff. ...
    (sci.electronics.design)