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
Every time I try to look up anything on my laptop it keeps saying my connection is not priavte what do I do
dangina [55]

You can click "Advanced" and still proceed to the website.


Please mark this answer as the Brainliest! Thank you :)




6 0
3 years ago
Read 2 more answers
You suspect a component in a computer is fried. You remove any unnecessary hardware devices one by one to narrow down where the
tankabanditka [31]

The examination phase

Further Explanation:

Hardware troubleshooting in computers requires a systematic and logical approach. Taking a logical approach helps you identify the root cause much easily. Ask yourself those questions first before getting to the bottom of anything. You will find it helpful to reproduce the problem and develop a hypothesis of the problem if you ask yourself those 20 questions.

Next comes the examination phase. Having gathered everything, I will now attempt a fix based on what I think I found. In my case, I suspect that there a component in my computer that is fried. A few ways to tell if my motherboard or components attached to the motherboard are fried is to remove the side panel first and examine the circuitry before removing any unnecessary hardware devices. Obvious sings will be smell of smoke. Examine the capacitors as well. Burnt capacitors have rounded tops. This is a clear indication that they are blown.

I will now remove every single component one by one from the motherboard and test my hardware on a low-level.

Learn more about computer hardware troubleshooting

brainly.com/question/12704715

brainly.com/question/13182488

#LearnWithBrainly

8 0
3 years ago
Examples of 15 viruses in computer
Zepler [3.9K]
Computer Viruses:

Morris Worm
Nimda
ILOVEYOU
SQL Slammer
Stuxnet
CryptoLocker
Conficker
Tinba
Welchia
Shlayer

Anti-viruses:

Esafe
Avast
Avira AntiVirus
e Trust Antivirus
Dr Web by
NOD32
F-Secure Antivirus
AVG Anti-virus
.Kaspersky Antivirus
McAfee Antivirus
eScan
PC-Cillin
Symantec Antivirus
8 0
2 years ago
Assume you have written a method with the header num yourMethod(string name, num code). The method's type is ____ .
elena-s [515]

A method is written with the header 'num' yourMethod(string name, num code). The method's type is <u>'num'.</u>

In the context of programming. a header refers to supplemental data placed at the beginning of a block of data being transmitted or stored. In the context of the Java method, the header is where you tell the Java program what value type if any, the method will return (a string value, an int value, a double value,  etc). As well as the return type, you require a name for your method, which is also placed in the header. You can pass values over to your methods in between a pair of round brackets.

You can learn more about method in Java at

brainly.com/question/28489761

#SPJ4

8 0
1 year ago
In the context of applications of artificial intelligence (AI), _____ perform well at simple, repetitive tasks and can be used t
Elina [12.6K]

Answer:

The right response is "Robots ".

Explanation:

  • A robot seems to be an independent machine that can detect its surroundings, conduct simulations, as well as take action throughout the modern or actual environment.
  • It is indeed a piece of computer-controlled equipment, which would also be utilized autonomously for carrying out duties or other hazardous tasks.
7 0
3 years ago
Other questions:
  • To change the background color of a page, which tab would you use?
    15·2 answers
  • Criminal Investigation people called my house on an automated voice is this a scam ??
    13·1 answer
  • When you write a C# program that stores a value in a variable, you are using temporary storage; the value you store is lost when
    12·1 answer
  • A computerized spreadsheet program is useful for
    6·2 answers
  • Words that have a special meaning in a programming language are called
    13·1 answer
  • Which tab do you select to change how you see your Word document on screen?
    9·2 answers
  • Where are the results from the Advanced Find feature displayed?
    6·1 answer
  • Which tool can effectively increase the curl of the subject’s lips?
    10·2 answers
  • What does ATM mean on lego mario mean I know that this is not school related but I trying to help my brother ​
    5·1 answer
  • You have been trying all day to check your direct messages on social media. The site is really slow to load and sometimes you ca
    13·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!