Lambda the Ultimate

The proof that sorting is at most O(n.log n) doesn't include the time taken to construct the proof ...

How is that relevant? Carter Cheng's trie is assuming the accept/reject state for every (potentially NP) string is already indexed and solved.

For an analogy to a sort, it's like arguing:

• I can construct a trie for all possible lists of inputs.
• Let the state associated with each location in the trie be the sorted list corresponding to that path in the trie.
• Following the path in the trie is O(n).
• Therefore, sorting lists is O(n).

We can index solved problems, but it seems we're missing a step with regards to solving the problems in the first place.

True enough there is a weakness there however. I suspect the second half of the arguments still stands i.e. unless one can show that john the ripper can crack passwords in less than exp time. You still have a case where the asymptotic complexity of a given algorithm is exp time and linear time via the verifier.

I think it is relatively easy to see that a physical number safe cannot be cracked (given a combination of some k depth)- in any other than exponential time (though the combination can be verified) in linear time O(n) which yields an non-P time exponential complexity.

The argument does however hold for arbitrary sized languages of finite size which is interesting.

I may need a third horn to make the argument completely water tight.

It's relevant because if he can prove that, for all languages, you can construct a DTM that takes polynomial time, it doesn't matter how long it takes to construct the DTM for a given language. It can be super-exponential and he would still have P = NP.

In your analogy, the time taken to construct the trie is irrelevant; you just need existence. The fact that the trie is infinitely large is the problem, since DTMs have a finite number of states. It is coincidentally true that you can't construct an infinite trie in finite time.

It can be super-exponential and he would still have P = NP.

This isn't true. A ONESAT instance is an example of a propositional formula which has exactly one solution which takes exponential time to discover (the problem is in NP.)

You can see a ONESAT problem as encoding a language which contains exactly one finite word, which a deterministic Turing program would accept in finite time, but for which it would take exponential time to construct that program.

Execution time of an algorithm depends on the input data, it does not depend on how hard it is to construct the algorithm. Surely this is completely obvious?

You can't disprove this by saying that some problems can be viewed as meta-algorithms constructing algorithms. It's still true for the meta-algorithms.

That is obvious. But you claimed that it wouldn't matter whether it would take him "superexponential" time. I concluded you meant an algorithm to go from a language description to a deterministic Turing program, and that does matter.

In this context we're mostly talking about parsing strings. We want an algorithm A that parses strings in a given language L and takes polynomial time in the length of the string, i.e. A is in P.

Then we want to prove that A exists for all L. So we might demonstrate an algorithm M which takes a description of L and creates algorithm A which is provably in P. M may well take super-exponential time in the length of the description of L, i.e. it's hard to construct A in general, but this doesn't affect that A is in P. M could be intractable on modern hardware but we'd still have the existence proof we need.

I think we're getting hopelessly mixed up here between different levels of algorithms. Maybe we should label A an "algorithm" and M a "proof".

The original point was just that you don't worry about how long it takes to produce A if you want to prove that A exists in P. i.e. "Where do you account for time to construct the trie?" where the trie is a step to creating the Turing program for A i.e. the time is accounted for in the running time of M.

Pushing complexity outside a carefully framed question in order to pretend it doesn't exist does not seem a very respectable way to prove an idea. Who in the mathematical community would accept it?

With regards to mathematical philosophies, I lean towards ultrafinitism. Consequently, I'm not inclined to consider M a proof. You can't actually construct M for problems of even moderate size.

Producing correct mathematics is a fairly respectable practice, and I think most in the mathematical community would agree. Membership of A in P is defined independently of M. We're not talking about the inherent computational complexity of producing parsers, we're talking about the inherent computational complexity of parsing strings. What more can be said on this?

Yacc is an M (that doesn't handle all languages). Writing yacc is not harder for bigger input languages ... but I won't explain why at risk of infinite recursion.

We're not talking about the inherent computational complexity of producing parsers, we're talking about the inherent computational complexity of parsing strings. What more can be said on this?

Well, you could also say: "We're not talking about the complexity of producing oracles. We're talking about the complexity of obtaining answers."

A more appropriate venue for Carter Cheng's question is cstheory.stackexchange.com. If you believe the proposed technique is respectable, test your hypothesis. Take it over there and find out.

If you think I have made an incorrect mathematical statement here, point out the concrete error. Otherwise, please accept that your original statement was inapplicable, for reasons I have gone to great trouble to explain in simple terms. Appeals to respectability, the mathematical community, or appropriate venues are not last-resort proof techniques in mathematics.

The proof technique Carter is attempting is "demonstrate a P algorithm for an NP-complete problem". Unlike many other techniques, this technique has not been proven to be invalid, and is not going to be invalidated here today, even if an attempt using this technique has been. But there we are again talking about problems and instances of problems as if the difference was clear.

Now let's accept our mistakes and move on ...

Mathematics are many and varied, depending on which axioms are accepted. A mathematical statement is only judged as correct with respect to a given set of axioms. Some mathematics (e.g. linear logics, ultrafinite) are more applicable to the physical constraints of CS than others. I won't say you're incorrect with respect to your axioms, just that the mathematics you are using does not seem to be physically valid.

One unrealistic assumption is that the resources to construct a proof (program) can be counted separately from its execution. Phase separation is common and useful technique, but there is never a true resource independence between the structure and size of a program or proof and its application. For one, time costs are not independent of space costs, e.g. the average cost of a lookup in the trie will depend on machine size on any physical machine.

Relevant to my earlier concern, the time to compute the proof (program) is never independent of the time to compute and use a proof. Phases are time-ordered, which implies they are not time-independent. Each phase must happen in the same physical reality. Many traditional mathematics are selectively blind to resource considerations. Such mathematics are, I believe, of dubious utility to CS.

I appeal to respectability and venue not as a "proof technique" but because one won't find any on LtU whom are passionate enough about the subject to explore the proof very rigorously.

This could be considered to be a nitpicky tangential to the main discussion here. Or it could be considered spot on topic. Bear with me a moment, I'll make the point.

[blockquote]
more applicable to the physical constraints of CS than others
[/blockquote]

I thought this choice of words was amusing. CS as a branch of mathematics has no "physical" limitations as such. It's purely about information.

But practical computation, as opposed to computer science, has physical limitations: speed, memory size, and bandwidth are all limited by the physical devices we compute with.

And reasoning about the constraints imposed by the physical limitations (how to most effectively use limited resources) is definitely one of the major subjects of study in CS.

Which brings us to P ?= NP. This is framed as a question with no "physical" constraints as such on solving it; This is a computer science (math) question, not a computation question.

But the question itself is about one of those things that is limited by a physical constraint on computation questions: speed.

If you posit that a complete solution to an NP problem can exist, and that if it exists then the NP problem can be solved in P time, then you're mixing up the computer science with the practical computation.

Finding that solution is supposed to be the practical computation part of the problem that IS physically constrained, and P ?= NP is a question about how that physical constraint applies.

If you craft a Polynomial-time method where a pre-existing solution is one of the "givens", then you have shifted the creation of that solution OUT of the domain of the practical computation whose physical constraints you are reasoning about and INTO the domain of the science question which has no physical constraints.

In other words, the domain in which the solution here is constructed renders it inapplicable to the problem it purports to solve.

And the phrase "Physical Limitations of CS" set off this line of reasoning and explanation because it jangled my sense of, well, inapplicability.

Ray Dillinger

Information is physical. A body of information has identity and history. Loss of information has a physical consequence of heat and entropy (cf. conservative logic). Today, we understand there is a direct relationship between information representation and physical state, including mass and energy. It is theorized that information may be the fundamental unit of our physical universe; albeit, below the level of the 'bit' (qbits, etc.).

Information theory is a study of correspondence in physical structure. Computation science is a study of controlled physical phenomena.

Or as Conor McBride so succinctly put it: CS is math for people who don't believe in telepathy.

(I suppose the phrase "purely about information", as though information were not a physical construct, jangled my own senses. CS is not about computers, but everything about CS is physical. Understanding this will aid you considerably for design at the extrema: very large scale and very small scale.)

You have shown that problems in NP have polynomial verifiers; that's part of the definition. You're neither close to understanding the problem, nor close to developing an intuition why the problem would fall either way.

I'm arguing against erroneous assertions here, not trying to prove P=NP. Although the latter might be easier, all told.

Well, you're not doing a great job so far.

Some, or all, problems in NP have polynomial verifiers, pending who you ask. The construction time does matter for the P=NP question, though you're right, the polynomial verifier is in P, which is also well known.

A tip: Your 'formal' reasoning is hard to read, and also is spurious with acronyms people need to guess at; I stated all you said in approximately two sentences. Don't do math when it's not necessary.

Actually, if P=NP, then you could write an algorithm finding algorithm that takes polynomial time ;)

Are there examples of algorithms which run in polynomial time on a Von Neumann machine but are super-polynomial on a Turing machine?

Long time ago. I only vaguely recollect log(n) or n added, or rather multiplied, complexity. But this was on moving from simple arithmetic (multiplying for example) to what they call 'bit complexity.' And that didn't even take into account moving a head around on a Turing machine tape. (Actually, I now remember the bit complexity on multiplication was very interesting: something like log(n)log(n)n.

I don't think the complexity analysis of radix trees takes into account the storage needed. On a turing machine, you need to skip a lot of tape to get to another node, an exponential number would certainly blow up the complexity.

And there is the other argument of the other thread that to store a language you'ld need to store an infinite number of finite strings.

Yes, I can visualize why it's harder to get to memory location 100,000 from memory location 0 on a Turing machine vs a Von-Neumann machine, but I can't prove to myself that this can make a P algorithm into a non-P algorithm, so I was wondering if there were textbook examples. I expect they involve VN machines with infinite memory, if they exist.

For that, I guess, you'ld assume O(1) moving from node to node on an abstract Von Neumann like machine, but it can be exponential on a Turing machine.

(Though constructing an exponential tree also takes at least exponential time and space even on a Turing machine.

But I don't really know a lot about Turing machines. I never read about them since I think they are the wrong abstraction for computation and most results are silly and unapplicable.

I don't mean the previous as a derogatory statement. Rather, I was interested, and looking into, schemes which are somehow comparable with what I think 'feels' right at better expressing abstract computation. And Turing machines always feel dated, and somewhat far-fetched to me, as an abstraction. Term rewrite systems, I think, are way more natural, and basic, than Turing machines. So I looked into complexity results on those, and never looked at Turing machines.)

Well yes, I agree, and underlying my question is, "am I allowed to prove P = NP using a Von Neumann machine, or would the proof be invalid until lowered to a Turing machine"? :)

No disrespect to the mighty Turing, of course.

I don't have the feeling it matters much. I just don't think that any proof of P=NP will be constructed with a Turing machine. The abstraction is just too crude for that.

No, but there definitely are algorithms that run somewhat faster on a random access machine than on a Turing machine. Binary search, for example.

It also depends on what you call a Von Neumann machine. If you abstractly assume that addresses can hold numbers of arbitrary size, the natural numbers, and all simple arithmetic operations are O(1), which people abstractly often do, that will certainly mess with the complexity if you want to know what that would mean on a Turing machine.

Right. That's why the random access Turing machine was invented. That gives you random memory access without allowing you to perform arithmetic on arbitrary length numbers in O(1). The way it works is that you have two tapes: one pointer tape and one memory tape. The pointer tape works like a normal tape, but you have an additional pair of instructions that read/write the memory tape at the location pointed to by the pointer tape. That's still not a physically accurate model of course: a trivial lower bound is that you can't do memory access in a O(n) size memory in less than O(n^(1/3)) due to the speed of light.

If superstring theory is to be believed, the lower bound is O(n^(1/9)), though with a very small constant. And that's still assuming causality.

:)

Ah yes, well spotted, spitting the password out is O(n) not O(1).

But why is password cracking not O(n)? If the password is stored in plain text and you include the verifier in your DTM, it's O(n), by my previous argument. If the password is not stored in plain text, but hashed (say) then you are saying that finding a hash collision is not O(n) (or more generally, is not in P). So prove that finding a hash collision is in NP but not in P, and you're done :)

I think the point you're missing is you're not allowed to have oracles / black boxes when showing something is not in P. You're only allowed oracles to show something is in NP, because of the verifier-based formulation of the set NP. In your case, since the oracle exists, clearly the problem is in NP. But it may also be in P.

(Effectively you're assuming that the best algorithm is brute-force search of the password space and asking the oracle each time; you're assuming the oracle can't be broken down and simplified.)

This is basically the crux of the issue. The problem is that hidden information is required however whether it is equivalent in principle to a program that employs the verifier directly.

In principle what results is a contradiction. Since unless one equates a brute force search of an unknown domain with apriori knowledge.

There is no contradiction here. What you call "hidden information" is exactly the crux of P vs NP. If you don't have it and you're just calling an opaque verification routine, then the question is trivial, as you note. The reason P vs NP is interesting is that if P=NP we have fast general program inversion. For example since we can write a program that checks whether a mathematical proof in some formalism proves a given theorem, inverting that we'd obtain a polynomial time algorithm that given a theorem computes a proof of it.

Thanks Edward. I suspect this raise some fundamental issues already- but you did give me an additional idea. consider a password cracker for which the string length is unknown apriori and the verifier runs in some unmeasured time that is proportional to the password string.

This does encode an infinite sized language (which rules out the use of the trie case) but at the same time shares similar properties to the fixed length K password case. Would this language fall into NP / P?

Asymptotically it should share the same characteristics and in principle given the infinite size one could not construct a radix tree based decider.

I don't think a variable length password fundamentally alters the situation. The point is, proving that something is not in P means mathematically proving beyond doubt that there is no possible reformulation that runs in P. No one has ever succeeded in doing this, for any problem in NP (it has been done for some algorithms not in NP, for instance the halting problem). It may appear that some problem is in NP \ P but I don't even know of an *approach* to proving that it is. Perhaps, proof by contradiction on the existence of an algorithm in P.

Yes, I think it's true that you can accept any finite language in O(n) just by having a large enough state machine (#states = 2^O(K)).

How are you going to encode the verifier on a random access Turing machine? Once you do so the program has knowledge about the verifier and it's not obvious that it can't go faster than exponential time. If you introduce a new computational model where John the Ripper has no internal knowledge about the verifier and can only make opaque calls to the verifier routine then indeed you cannot do better than exponential time, but that's not the model that P?=NP is about.

Actually turing machines arent completely random access since this would imply constant access of all memory locations (TM's require head movement).

This actually does not require a new computational model. I can be expressed already within the TM framework.

Encoding a verifier is straight forward one just walks the tape left to right one and accepts only if all the letters match for each location O(n) time worse case. One can easily see a finite state automaton does this.

Carter, you're not seeing the point. The "black box" is part of a new computational model. Otherwise, it's a transparent box, and you can potentially optimize the search.

Crank territory? Harsh. Students learn by thinking they can take on things like P = NP and finding out why they can't. If Carter had a webpage called "P = NP is obvious and mathematicians are all stupid" then I'd agree with the crank label.

As for off-topic ... well, he did mention languages :)

I intended that comment to mean "this is the kind of thing you'd find on a crank's website" rather than "you are a crank", but maybe it was too harsh. My apologies, Carter.

But it is a bit hard to tell as some of the responses above are not threaded / split into multiple threads. Basically definition 1 is not a formal language in the conventional sense, it corresponds to the set of problems that can be solved by a FSM rather than a TM. As a result of the reduction in power you get a different hierarchy of complexity classes and hence the apparent p=np result. You might be interested in parameterised complexity, which is the area in complexity theory that investigates this technique.

The questions are from the "not even wrong" category, most answers can be found by just Googling.

1) Why don't TM based trie (radix-tree) like data structures trivially decide any language in O(n) time (and thus yield a trivial solution to P = NP since every deterministic Turing Machine is a nondeterministic one)?

A radix tree "recognizes" words in a finite set and is in construction equivalent to a deterministic finite automaton. A deterministic finite automaton (DFA) recognizes only regular languages, and even a DFA can have an exponential state space, which means not even a DFA will accept a language in polynomial time in all cases.

2) If this is the case it would seem that there is something wrong with the definitions of NP and P in that having a DTM or NTM decide a language may not be strong enough to capture what someone means by a language.

It isn't the case.

3) There are obviously cases of languages that seem to be decided by algorithms which are in NP but not P. An example would be something like a generalized password cracking tool akin to John the Ripper(for those security gurus).

John the Ripper decides whether a word is in a language by an exponential search over the state space. It just happens that the state space is rather small, thus the exponential search terminates in acceptable time.

As I stated, there are intuitions why "P != NP" and why "P = NP". If you have an intuition either way, then it can be formalized and studied. But none of the above is even close to an intuition.

A deterministic finite automaton (DFA) recognizes only regular languages, and even a DFA can have an exponential state space, which means not even a DFA will accept a language in polynomial time in all cases.

It should be clear to anyone who remembers the definition of a DFA that they accept or reject in linear time. Regular languages are in P. They simply call for Turing machines with very many states. Historically, reduction to Universal TMs was meaningful when studying computability (and not complexity), but there seems to have been some recent development in small UTMs that preserve polynomial-time complexity.

Finally, note that deciding a given regular language is quite a different task from deciding a pair of [the description of a regular language] and [a string]. The latter is still in P, but not linear time. I suppose the most intuitive way to prove this is to code a set-of-state NFA simulation. The number of iterations is linear in the length of the input string, and each iteration takes time linear in the size of the NFA description (modulo epsilon-transitions). The same is true for CFLs; that's why deciding a given CFL is, in the worst case, cubic-time, but CFG itself is P-complete.

As far as I remember, the negation of a DFA might grown exponentially. (A bit different from what I stated before.)

Anyway, what I know for sure, is that going from an NFA to a DFA can result in an exponential blowup.

Moreover, the construction from a DFA from a regexp might be linear, but that's hardly interesting if the regexp has an exponential size, which was the interesting question in the original post.

Computing the negation of a DFA can take a long time. However, once it's computed, the resulting (potentially very large) automaton still accepts or rejects any input in linear time.

Which was exactly my point. There are languages which can be recognized by a DFA but for which the state space is exponential.

If you're linear in an exponential term, then I would say it's exponential.

(His original claim is on languages, not _only_ on regular languages.)

(there are regular languages for which the minimal DFA of the reversal is exponentially larger than the minimal DFA of the language)

The linear time is in terms of the input: the string for which membership must be decided. Really, this is a fundamental distinction. Any given DFA decides any input string in linear time. Simulating unknown DFAs on a TM isn't as trivial. I'm not sure what you mean by DFAs for which the state space is exponential, though: in terms of what is it exponential? Certainly not the input string, as the DFA is fixed before receiving the strings.

Again, there is a difference between the time complexity of a TM that decides a given regular language (for any regular language, there exists a TM that decides whether the input string is in that language in linear time, e.g. by reduction to a DFA), and one that decides whether the regular language described by its first argument includes the string given as its second argument (which is still polynomial time, e.g. with the classic set-of-state algorithm).

In the first case, we have Language -> String -> Boolean, and are interested in the time complexity of String -> Boolean, with arbitrary processing performed in the first arrow (which is why we don't even bother to talk about a description of the language, and instead consider an abstract Language). This would correspond to compiling a regular expression once, and then using it very many times.

In the second case, we have, for example, (NFA-description, String) -> Boolean. This can still be done in polynomial time, but quadratic in the length of the description and of the string (in fact it's the product of both).

There are regular languages for which the minimal DFA of the reversal is exponentially larger than the minimal DFA of the language. (Remember, were still talking recognizing all languages in polynomial time.)

Anyway, it doesn't matter. From NFAs we know that DFAs can grow exponentially in size, therefor it holds that there are languages for which the DFA is exponential in terms of the description. Therefor, the original construction in 1) fails to recognize all languages in polynomial time.

(Ah. I might have gotten reversal wrong with negation; the latter is trivial. Oops, my mistake. The rest of the arguments still hold though.)

I agree. How does that lead us to "not even a DFA will accept a language in polynomial time in all cases."? In any case, I referred to the NFA-based set of state simulation for the case when the regular language is also given as an input.

How does that lead us to "not even a DFA will accept a language in polynomial time in all cases."?

There are languages for which the description as a NFA will have an exponential equivalent DFA. Therefor it doesn't even hold that all languages with short descriptions can be recognized in polynomial time (with a DFA, which is the construction in 1)).

Ah, if I understand you correctly, you're asserting that there is no TM that can simulate an arbitrary DFA on a string in time polynomial in the length of the string. Given that the runtime would be independent of the size of the (complete) input, it seems trivially true.

No, I am asserting that there is a language for which the DFA which recognizes it is exponential in size of its description. Therefor (contrary to the original claim) you can't recognize _all_ languages in polynomial time with a DFA.

The runtime of a DFA is measured in the number of state transitions, and is therefore independent of the number of state in the DFA. Any DFA executes in time linear in its input's length, and there are UTMs that can simulate arbitrary DFAs in polynomial time.

Independently of that, there are languages that are not regular, and thus cannot be decided by finite state automata (deterministic or not). The reason a DFA won't work is that not all languages can be decided by FSA, not that some DFA run in time super-polynomial in their input's size.

The reason a DFA won't work is that not all languages can be decided by FSA, not that some DFA run in time super-polynomial in their input's size.

God man. I give up. If you read the original argument, you'll see that I stated that a DFA cannot encode all languages (here we agree), moreover, cannot even recognize all simple languages in polynomial time (this you seem unable to understand).

I know what a regular language is, and so I can see that it takes linear time for any string to accepted or rejected by a deterministic finite automata. (it remove one symbol at each step so it can't take any longer than linear time)

But what is a simple language?

But what is a simple language?

The original poster thought he had a construction by which _any_ language could be recognized in polynomial time. A simple language I left underspecified, but you can for instance take a language accepted in polynomial time but described by a DFA exponential in size, and probably you could take a language recognizing matched parenthesis, or composite numbers, etc.

(I guess you could formalize 'simple' as any language which can be recognized in polynomial time.)

Look, it is really trivial: A language is recognized in polynomial time if the program which recognizes it takes a polynomial number of steps in terms of the (length of the) input word to recognize it.

A DFA cannot recognize all languages, moreover, a DFA might take an exponential number of steps recognizing specific strings. For the latter, take a DFA of polynomial size for which the reversal results in a DFA of exponential size. You can trivially construct a program which recognizes this language in polynomial time (reverse the string, see whether the DFA accepts it), but for which the DFA of the reversal would take exponential time since it needs to go over a finite automaton of exponential size to see whether it would recognize that string.

Thus, DFAs cannot recognize all languages in polynomial time, moreover DFAs cannot even recognize regular expressions in polynomial time in terms of (the length of) the input word.

(This is all pending that reversal of a DFA can exponentially blow up. That might be a result depending on P!=NP in a nontrivial manner, but I doubt that.)

First, I'll argue from authority: http://qwiki.stanford.edu/index.php/Complexity_Zoo:R

The class of regular languages is exactly the set of languages decided by DFAs or NFAs, and equal DSPACE(O(1)).

When discussing asymptotic time or space complexity, the bound is function of the input's length, in this case, the string to be accepted or rejected. It's a basic result that regular languages are decided, e.g., by DFAs, in linear time. I believe it's even an early exercise in Sipser. In any case, it should be clear that a deterministic TM that only uses a constant space on the read-write tape can either loop forever or terminate after a number of steps linear in its input (again, the string to decide).

So, when you write that the size of the DFA might be exponential, it makes no sense: the size of the DFA isn't a function of the size of the input string. You're right, the DFA might be very large, but we're interested in asymptotic behaviour. For any DFA size (any natural), there is an infinity of strings that are much larger than that size.

Again, I think the hypothesis you're not stating is taking the DFA's description to be part of the input. When we reduce DFAs to TMs, the DFA's state are usually encoded as-is in the TM's state.

Still, using an UTM to interpret a DFA would still be polynomial in the size of the DFA and of the string, even if the DFA is very large: as you pointed out, if the DFA's description is very long, that description is also part of the input. It might seem circular, but, as I wrote earlier, not taking the DFA's description into account results in useless bounds when we pass ever-growing DFAs but tiny strings.

Finally, one could also use an UTM to interpret an NFA, and still be polynomial in the size of the NFA and of the string. Again, the set of states construction (or derivative-based, or lazy compilation to DFA, different names for very similar approaches) will run in time polynomial in the total input length, i.e. the sum of the size of the NFA's description and the input string's length.

Every language decided by a DFA is decided in time linear to the length of the input. There is no regular expression that isn't decided in linear time by a DFA. If you don't believe me, construct one, and prove that the resulting DFA runs in super-polynomial (or just super-linear) time; any success will result in a solid paper.

After mucking around a bit, I guess it is time to write down some stuff.

Definition 1: A 'simple' language is a language of words which are recognized in polynomial time by a Turing program. 'Recognize' means that the Turing program will either write 0 to the tape for a rejection, or 1 for acceptance, and halt.

Lemma A: Turing programs which simulate a DFA cannot recognize all 'simple' languages. (The DFA is not part of the input, but part of the tape.)

Proof of A: This is trivial. Take "matching parenthesis" or "composite".

Lemma B: There are 'simple' languages for which a Turing program simulating a DFA would run in exponential time to the input size. (The DFA is not part of the input, but part of the tape.)

Proof of B: Take a DFA of polynomial size, but for which the reversal has an exponential state space. Then the language described by that DFA is 'simple'; the reversal of the language is also 'simple' by construction of the program which first reverses an input string, then runs the original program on it. The Turing machine which simulates the DFA describing the reversal of all input strings of the original DFA can't be 'simple', since the state space of that DFA is exponentially larger than the original state space, therefor it will take a Turing machine exponential (more) time to construct the TM which will accept an input string.

Ah fuck, I see it. The TM program size is never taken into account, whereas I naturally do that since it matters for P vs NP, and I only think in terms of term rewrite systems. The equivalent statement of lemma 2 in 'Turing machine language' would be something like "it would take exponential time to construct the polynomial verifier for the negation of some 'simple' languages," whereas I only looked at the exponential size of the term.

I hate Turing machines, everything about them is wrong.

I'm a little embarrassed to ask, as I hadn't been following this thread closely until the definition and lemmata caught my eye, but I'd appreciate some clarifications re the definitions you're using, as I'm not getting them. (Really not trying to be difficult, just to understand.)

You say a simple language is a language of words recognized by a Turing program. By "word" do you mean "string that may be the input"? To my understanding one recognizes a language, i.e. a set of strings, rather than recognizing a particular string. I've never encountered the term "Turing program" before; I'm familiar with what I've always understood to be a standard notion of a Turing machine, but now I'm wondering if that's a bit different.

You describe a Turing program simulating a DFA by saying the DFA is part of the tape rather than part of the input. Evidently this isn't a Turing machine such as I'm familiar with, since there the tape is the part of the machine that is read-write, and the input is provided by placing it initially on the tape.

As far as I am concerned, this whole thread shows why Turing machines are a lousy abstraction for thinking about complexities. If everything would have been phrased in terms of a better abstraction model, we wouldn't have arrived at the mess we're at now.

Moreover, I don't get Turing machines since I don't like them.

Yeah, I got the construction of the Turing machine wrong since I somewhat naturally assume that the DFA is part of the tape, leading to complexity results I even don't find natural.

The problem is that the only right way to look at it is that you can end up with an exponential sized program which can take linear time to accept a string. This is the only relevant part.

Now, there are two manners in which a TM looks at that: The DFA is in the state transition system and its size is dismissed - which you can't really do, or the DFA is on tape - which leads to an exponential time recognizer.

Hence I really, really, don't like TMs.

(Not that I am that good at math, though...)

or the DFA is on tape - which leads to an exponential time recognizer.

The runtime would be an exponential function of *what*? Simulating a DFA on a string, with both given an arguments, is still polynomial time.

The recognizer would be an exponential function of *what*?

Exponential in size of the word being recognized.

Simulating a DFA on a string, with both given as arguments, is still polynomial time.

I find this a non-result. Polynomially bounded w.r.t. to a term of exponential size? Another 'skewed' complexity result byproduct of an inadequate abstraction.

Again, for the P=NP construction the only thing which matters is that you can construct a polynomial verifier in polynomial time. An exponential sized verifier will not do, whether the thing exists in the state transition machine, or it exists on tape. (I don't even want to think about a mix of that.)

Come on. Nitpicking. You understand the complexities as well as I do.

(Anyway, seems to me that we're running around in circles here. Let's end the thread.)

The recognizer —the finite-state machine that controls the machine, analogous to the CPU of a computer— is fixed. It does not vary at all with the size of the input. I brushed against this point earlier when I mentioned that the recognizer doesn't recognize a word, it recognizes a language. That is, this fixed machine will take an input of any size whatsoever, and will determine whether that string belongs to the language that the machine recognizes.

Given DFA, D, that directly recognizes language L, you can systematically create DFAs for many other languages. Examples include negate-L or reverse-L or L². Formally, in an appropriate context, one can consider D to be a specification of these other languages. Simulation of D does not directly recognize these other languages, but it seems Marco is assuming the full range of indirect recognition.

Formulation of a DFA to recognize negate-L is trivial: simply invert the accept and reject states. But the formulation of another DFA to recognize reverse-L may in general be exponential effort in the size of D. (Yet, it would be trivial to recognize reverse-L if we had the freedom of a stack machine.)