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
What report provides data on how specific sections of a website performed?
zalisa [80]

Answer:What report provides data on how specific sections of a website performed? 100% Correct Answer: Content Drilldown report

Explanation: sorry if it’s wrong

3 0
2 years ago
For your biology class, you have taken a number of measurements for A plant growth experiment. you wish to create a chart that s
Natasha2012 [34]
The answer is B, calc or excel
4 0
3 years ago
Write a function named ilovepython that prints out I love Python three times. Then, call that function.
Brums [2.3K]

Answer:

The program to this question can be described as follows:

Program:

def ilovepython(): #defining a method

   for i in range(3): #defining a loop that print messasge three times

       print('I love Python')#print messasge

ilovepython() #calling the method

Output:

I love Python

I love Python

I love Python

Explanation:

Description of the python program can be described as follows:

  • In the above Python program, a method "ilovepython" is defined, inside the method a for loop is used, inside the loop print method is used, that print the message "I love Python".
  • In python for loop is used to iterate over series and we can execute a set of statements with the loop, tuple, series, once for each element in the list.
8 0
3 years ago
You can view the existing Access Control Lists for a set of folders on a Windows system by right-clicking the folder you want to
NikAS [45]

Answer:

And clicking the security tab option.

Explanation:

Lets explain what an object's ACL is. I will use an example to best explain this. Let's suppose that user Bob would want to access a folder in a Windows environment. What supposedly will happen is that Windows will need to determine whether Bob has rights to access the folder or not. In order to do this, an ACE with the security identity of John will be created. These ACEs are the ones that grant John access to the folder and the ACLs of this particular folder that John is trying to access is a list of permissions of everyone who is allowed to access this folder. What this folder will do is the to compare the security identity of John with the folders ACL and determine whether John has Full control of the folder or not.

By right clicking the folder and selecting the security tab, John will be in a position to see a list of the permissions (ACLs) granted to him by the folder.

3 0
3 years ago
5 examples of a linear motion in object.
NNADVOKAT [17]

An example of linear motion is an athlete running 100m along a straight track. Linear motion is the most basic of all motion. ... Neglecting the rotation and other motions of the Earth, an example of linear motion is the ball thrown straight up and falling back straight down.


3 0
3 years ago
Other questions:
  • You are troubleshooting a network issue on a client computer and discover that the network card has an IP address of 169.254.196
    6·1 answer
  • Speech on inventors and inventions
    14·1 answer
  • Ming is building an inexpensive computer to use for her online classes, and needs to purchase Windows. What is the most cost-eff
    8·1 answer
  • PLS HELP!!
    13·1 answer
  • Tim has an old server computer that his company uses as a backup. One of the hard drives has gone bad and needs to be replaced.
    13·1 answer
  • By default, windows does not display ____________________ in windows explorer.
    8·1 answer
  • To create a new folder, press ____.
    12·1 answer
  • __________ offers a mechanism to accomplish four security goals: confidentiality, integrity, authentication, and nonrepudiation.
    9·1 answer
  • Random Walker Collisions In lecture, we saw how to model the behavior of a random walker on a 2D grid using a Monte Carlo simula
    8·1 answer
  • I need a C++ program to ask the user to put in different numbers until zero is pressed then the program counts the numbers that
    10·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!