Re matches a string shorter

Reference no: EM131009467

Theory (11 points). In the blanks mark each of the statements below as true (T) or false (F).

A. _____ No RE matches a string shorter than itself. B. _____ Any RE without closure (* or +) describes only finitely many strings. C. _____ No problem in NP can be solved in polynomial time. D. _____ It is possible to write a program that goes into an infinite loop if a given Java program goes into an infinite loop and terminates otherwise. E. _____ If P equals NP, every problem in NP is NP-complete.

F. _____ No Turing machine can decide whether a given DFA halts on an arbitrary finite input. G. _____ The Church-Turing thesis cannot be proven mathematically. H. _____ If P equals NP, then the Traveling Salesperson Problem can be solved in polynomial time by a deterministic Turing Machine. I. _____ If P does not equal NP, then the Traveling Salesperson Problem is not in P. J. _____ Factoring is known to be in NP but has not been proven to be NP-complete. K. _____ The discovery of a polynomial-time algorithm for TSP would not imply a polynomial-time algorithm for factoring.

Reference no: EM131009467

Questions Cloud

Can you express sympathy with someones negative situation : Can you express sympathy with someones negative situation without apologizing for the circumstances? Explain your answer - Is intentionally deemphasizing bad news the same as distorting graphs and charts to deemphasize unfavorable data?

How do they support party systems around which they arose : Compare and contrast single-member districts and proportional representation (PR). How effective is each electoral system in representing its people's interests? How do they support the party systems around which they arose

Prompts user to enter 7 elements : Write a java application that prompts user to enter 7 elements. The elements will be stored in an array list of type double. All elements entered should then be displayed on a separate line. The sum of the elements should also be shown in the end li..

What the relationship between interest groups and government : Understanding this, what is the relationship between interest groups and government? How does this apply to government-created interest groups

Re matches a string shorter : A. _____ No RE matches a string shorter than itself. B. _____ Any RE without closure (* or +) describes only finitely many strings. C. _____ No problem in NP can be solved in polynomial time. D. _____

What would you conclude from these results : Much has been made of the concept of experimenter bias, which refers to the fact that for even the most conscientious experimenters there seems to be a tendency for the data to come out in the desired direction. Suppose we use students as experime..

Following names with an associated phrase : Name game (8 points). Match the following names with an associated phrase. Use each letter once and only once. A. Steve Cook _______ Incompleteness B. Alan Turing _______ Reductions

Identify and describe current issue in american government : Identify and describe a current issue (this could be a controversy or just an issue of importance) in American Government. Explain in 1-2 pages how one of the modern philosophers we've studied would respond to that issue

What is the value of r : TOY Consider what happens when the following TOY program is executed by pressing RUN with the program counter set to 10: 10: 8110 R[1] A. What is the value of R[1] after the instruction at location 10 completes? B. What is the value of R[2] after ..

User Account

All Pages