1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
viva [34]
3 years ago
7

Under the assumption that there exists an unknown Turing machine encodableinc1bits that decides3-SATis inO(n10) time, give imple

mentation details for a Turing Machine M that decides 3-SAT in O(n10000) time.
Computers and Technology
1 answer:
zmey [24]3 years ago
7 0

Answer:

3. (9 points) The goal of this problem is to show that our formal definitions of P and NP imply that P = NP cannot have a non-constructive proof. Throughout this problem we assume a consistent, binary, encoding of both Turing machines and 3-SAT instances. Note that the complexities are intentionally not tight to address potential overheads from scan- ning the tape linearly in order to look for certain symbols. (a) (3 points) Show that for any constant cı, there is a constant c2 such that if Mi is a Turing machine encoded by at most bits that correctly decides 3-SAT in O(n10) time (aka. 3-SAT E TIME(n10), then there is a Turing machine M, encoded by at most most c2 bits that runs in O(n100) time such that if the 3-SAT instance has a satisfying assignment, M, accepts and writes a satisfying assignment at the end of the tape. (b) (3 points) Let M ...Mbe Turing machines show that the language {(k, M... Mk,t,w) | w is an instance of 3-SAT and one of M, writes a satisfying assignment to w in at most t steps can be decided by a Turing machine in (k2107 10) time. (c) (3 points) Under the assumption that there exists an unknown Turing machine encodable in c bits that decides 3-SAT is in O(n10) time, give implementation details for a Turing Machine M that decides 3-SAT in O(n10000) time. Hint: the constant factor in the big-O is able to hide any function related ci and c2, which independent of input sizes, and thus constants.

Explanation:

3. (9 points) The goal of this problem is to show that our formal definitions of P and NP imply that P = NP cannot have a non-constructive proof. Throughout this problem we assume a consistent, binary, encoding of both Turing machines and 3-SAT instances. Note that the complexities are intentionally not tight to address potential overheads from scan- ning the tape linearly in order to look for certain symbols. (a) (3 points) Show that for any constant cı, there is a constant c2 such that if Mi is a Turing machine encoded by at most bits that correctly decides 3-SAT in O(n10) time (aka. 3-SAT E TIME(n10), then there is a Turing machine M, encoded by at most most c2 bits that runs in O(n100) time such that if the 3-SAT instance has a satisfying assignment, M, accepts and writes a satisfying assignment at the end of the tape. (b) (3 points) Let M ...Mbe Turing machines show that the language {(k, M... Mk,t,w) | w is an instance of 3-SAT and one of M, writes a satisfying assignment to w in at most t steps can be decided by a Turing machine in (k2107 10) time. (c) (3 points) Under the assumption that there exists an unknown Turing machine encodable in c bits that decides 3-SAT is in O(n10) time, give implementation details for a Turing Machine M that decides 3-SAT in O(n10000) time. Hint: the constant factor in the big-O is able to hide any function related ci and c2, which independent of input sizes, and thus constants.

You might be interested in
Research shows that a passive close to a cover letter leads to more interviews. Please select the best answer from the choices p
Alchen [17]
The answer is False.

According to research, a passive close doesn't lead your cover letter to have more interviews. In writing the closing part of your cover letter, it is easy to have a passive sentence but it sounds like less confidence to the employer. The last part of the cover letter should contain strong content to give an impression to the person who reads.
6 0
3 years ago
Read 2 more answers
_______ allows you to add formatting such as shapes and colors to text. a. worddraw b. wordart c. worddesign d. wordshapes
4vir4ik [10]
Word Design is the answer.
4 0
3 years ago
Read 2 more answers
How to call a variable as a tag in react native.
Pepsi [2]

Explanation:

There is no need of adding template strings inside a <Text> component for adding strings in react-native. You can just use simple text and for variables, you can wrap it with curly braces

6 0
2 years ago
Match the following: B. Static libraries A. Dynamic Link Libraries (DLL) - Using static libraries - Making some changes to DLL A
TiliK225 [7]

Answer:  hello your question is poorly written and I have been able to properly arrange them with the correct matching

answer

Static libraries :  C

Dynamic link libraries:  A

Using static libraries:  B

Making some changes to DLL:   D

Explanation:

Matching each term with its meaning

<u>Static Libraries </u> : Are attached to the application at the compile time using the Linker ( C )

<u>Dynamic link libraries</u> ( DLL ) : Is Loaded at runtime as applications need them ( A )

<u>Using static Libraries </u>: Makes your program files larger compared to using DLL ( B )

<u>Making some changes to DLL </u>: Does not require application using them to recompile ( D )

8 0
3 years ago
Lập trình web truy vấn csdl và hienr thị ra màn hình danh sách các bản ghi
almond37 [142]

Answer:

ExplanatOverfishing occurs "when more fish are caught than the population can replace through natural reproduction," according to the World Wildlife . Once this occurs, the species is no longer "sustainable." Eighty-seven percent of all the world's fish stocks that we know about are at the "breaking point," according to the Environmental Defense Fund (EDF).

ion:

3 0
2 years ago
Other questions:
  • Use a colon before a list and put one space after a colon. True False
    15·2 answers
  • Of the three different types of résumé formats (chronological, functional, or combination), which format would you use to create
    11·2 answers
  • The font color grid is located in the color group on the design tab. (points : 2) true false
    9·1 answer
  • Which is technologically backward country? Options United States U K CHILE INDIA
    14·1 answer
  • In a linked chain implementation of a queue, the performance of the enqueue operation
    14·1 answer
  • Despite the rise of messaging apps and other forms of social media, these efforts are focused on consumer efforts, with corporat
    7·1 answer
  • Which element can be changed using the Print pane? Check all that apply.
    9·2 answers
  • Write a technical term for following statements
    15·1 answer
  • An installation is:<br> please help asap
    11·1 answer
  • Given a number n, for each integer i in the range from 1 to n inclusive, print one value per line as follows:
    12·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!