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
Select the correct answer from each drop-down menu
Lana71 [14]

Answer:

The purpose of the domain name is for credibility and location purposes.

Explanation:

For example.

nz.gov means that the domain owner is the government on New Zealend

8 0
2 years ago
Help please not trying to fail
deff fn [24]

Answer:

B. Everywhere CFCI is not

8 0
3 years ago
How would you describe the difference between a syntax error and a logic error?
Ugo [173]

Answer:

hii

Explanation

syntax error:  a syntax error is an error in the syntax of a sequence of characters or tokens that is intended to be written in compile-time. A program will not compile until all syntax errors are corrected.

logic error:  logic error is a bug in a program that causes it to operate incorrectly, but not to terminate abnormally. A logic error produces unintended or undesired output or other behaviour, although it may not immediately be recognized as such.

6 0
3 years ago
Read 2 more answers
Building relationships during your career exploration is called
elena-s [515]
Building relationships during your career exploration is called networking. This is when you are forming relations with those around you so that opportunities may turn up.

Your answer is: Networking 

Have an great day mate!
6 0
3 years ago
Read 2 more answers
Can someone tell me how to fix the keyboard on ipad?- its in the middle of my screen andd i dont know how to do it
mamaluj [8]

Answer:

Here

Explanation:

To move keyboard to bottom of screen, you just need to tap and hold the keyboard icon at the bottom-right corner of the keyboard, choose Dock option. To fix iPad keyboard in middle of screen, please tap and hold the keyboard icon, then choose Dock.Nov 5, 2020

5 0
3 years ago
Other questions:
  • Which word processing file that contains text and other
    13·2 answers
  • When a Python script is running as a standalone program, what will the __name__ variable be set to?
    7·1 answer
  • The Internet is considered a WAN. *<br><br> True<br> False
    9·1 answer
  • I have $80 and I want a smartphone that you can call for free what should I get
    14·2 answers
  • A service technician removed the inspection/fill plug from the differential of a rear-wheel- drive vehicle and gear lube started
    8·1 answer
  • What are 3 software programs for mobile computing?
    10·1 answer
  • Pick one of the following scenarios and
    6·1 answer
  • Moving your Sprite from right to left is considered the X coordinate?
    5·1 answer
  • I think you have been doing a great job but you haven’t been signing many people up for our new service feature I want you to se
    8·1 answer
  • explain why you can determine machine epsilon on a computer using IEEE double precision and the IEEE Rounding to Nearest Rule by
    7·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!