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
Use the function varimp() on the output of train() and save it to an object called imp:_____.
Orlov [11]

Use the function varimp() on the output of train() and save it to an object called imp object.

<h3>What is the classification that has More than Two Classes and the Caret Package</h3>

In the Classification that has More than Two Classes and the Caret Package section, one need to use the methods that can be able to adapt to higher  forms or dimensions and through a lot of different machine learning algorithms.

Note that varImp is seen as a generic method for calculating variable .

Hence, Use the function varimp() on the output of train() and save it to an object called imp object.

Learn more about Computer function from

brainly.com/question/17048576

#SPJ1

5 0
1 year ago
Using caller id is part of which step in an effective time management plan
timurjin [86]
The answer is avoid distractions.  <span>Using caller id is part of  step to avoid distractions in an effective time management plan.  </span><span>Today with caller ID available you can identify your callers. When you are focused on your task at hand and the time you have to accomplish it, you must learn to better control the telephone. </span>
5 0
3 years ago
The first row in a table is referred to as the _____ row and the last row is considered the _____ row.
Juliette [100K]

the first row in a table is classed as the header row.

and with the last one I'm not sure because as far as I know there's not considered a last row.

6 0
3 years ago
• In your response, please include some examples of the three different types of storage.
babunello [35]
Hard Disk Drive
Solid State Drive
And Random Access Memory (RAM)
6 0
3 years ago
Read 2 more answers
Sending an identical message in an e-mail blast to all customers is an example of
disa [49]

Answer:

Broadcast message

Explanation:

A broadcast message is an identical message sent to a lot of recipients. When it is an email, it can be sent in Carbon Copy (Cc) or a Blind Carbon Copy (Bcc) form.

With the<em> Carbon Copy</em>, every recipients will be notified about the other recipients. In most cases all the email usernames of the recipients will be sent to all the recipients individually.

With the <em>Blind Carbon Copy</em>, every individual sees the message as he/she received it alone. The individual is not notified about the other recipients.

8 0
3 years ago
Other questions:
  • Technician A says that the last step in the diagnostic process is to verify the problem. Technician B says that the second step
    12·1 answer
  • If you enjoy working with livestock, the best cluster in which to research careers would be: A. Health Science. B. Agriculture,
    11·1 answer
  • Write a program that does the following: • Alphabetizes a list of small (non-capital) letters. For consistency, make the string
    14·1 answer
  • Write a program whose input is two integers and whose output is the two integers swapped. Ex: If the input is: 38 then the outpu
    11·1 answer
  • The building blocks of coded language are called
    11·2 answers
  • Which function calls would provide the most helpful test of this function? Remember: With tests, you are attempting to figure ou
    5·1 answer
  • You have been supporting CSM Tech Publishing's Windows Server 2016 server network for over a year. The office has two Windows Se
    12·1 answer
  • E commerce is the demand of modern society both for time and money
    14·2 answers
  • Write a q basic program to find the sum of all the even numbers from 1 to 50​
    14·1 answer
  • 4. Compute the following additions
    7·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!