Tag: polynomial

Provide a polynomial time algorithm that decides whether or not the language recognized by some input DFA consists entirely of palindromes

Everything needed to know is in the question statement. I believe that the DFA has to be acyclic (meaning its language is finite), which can be checked in polynomial time. However, finding all paths from the start state to an accept state can run in exponential time in worst-case.

I can verify solutions to my problem in polynomial time, how would a non-deterministic algorithm arrive to a solution if it always takes $2^n$ bits?

Decision Problem: Given integers as inputs for $ K$ and $ M$ . Is the sum of $ 2^k$ + $ M$ a $ prime$ ?

Verifier

m = int(input('Enter integer for M: ')) sum_of_2**K+M=int(input('enter the sum of 2^k+m: '))  if AKS.sum_of_2**K+M == True:    # Powers of 2 can be verified in O(N) time   # make sure there is all 0-bits after the 1st ONE-bit      # Use difference to verify problem    if sum_of_2**K+M - (M) is a power_of_2:     OUTPUT Solution Verified

The powers of 2 have approximately $ 2^n$ digits. Consider $ 2^k$ where $ K$ = 100000. Compare the amount of digits in $ K$ to the amount of digits in it’s solution! Also take note that the powers of 2 have $ 2^n$ bits as its 0-bit Unary essentially for the exponent $ n$ .

Question

How would a non-deterministic machine solve this problem in polynomial time?

Nondeterministic polynomial time algorithm versus certificate/verifier for showing membership in NP

In this paper (https://arxiv.org/pdf/1706.06708.pdf) the authors prove that optimally solving the $ n\times n\times n$ Rubik’s Cube is an NP-complete problem. In the process, they must show that the relevant decision problem belongs in NP (section 2.5 on page 6). To do this, they describe an algorithm that nondeterministically solves the Cube in polynomial time. It seems to me that this is more effort than necessary.

In particular, the relevant decision problem is as follows: The Rubik’s Cube problem has as input a permutation $ t$ and a value $ k$ . The goal is to decide whether $ t$ can be solved in $ k$ or fewer moves. So rather than constructing a nondeterministic polynomial time solution algorithm, they could simply give a certificate that a "yes" decision is just a list of at most $ k$ moves and verify that checking this is polynomial time.

So my questions are as follows. Are the two definitions below actually equivalent?

  1. NP is the complexity class of decision problems that are solvable by a nondeterministic Turing machine in polynomial time.
  2. NP is the complexity class of decision problems for which a solution can be confirmed in polynomial time (deterministically)?

And if they are equivalent, why would the authors of the linked paper choose the more difficult method (or am I wrong about this assumption)?

Note that I am posting this question on multiple StackExchange websites as I’m not sure where it’s best fit. If it is inappropriate here, I’ll happily delete it. Similarly, I’ll link to a good solution on another site if it gets answered there.

How do I decode a received polynomial code with an error?

As a message I get (5,0,1,3), which is coding a sequence of numbers of length 2 in $ \mathbb{F}_7$ as polynom with the 4 support points a1 = 0, a2 = 1, a3 = 2, a4 = 6. In the transimission occured an error. Calculate the original message.

How do I do this? In my script we didnt’t talked about polynomial codes directly just about the cyclic code. And the topic of this exercise is polynomial codes.

Could someone please get me through this or explain a way? Thanks for any help!

Given an algorithm, decide whether it runs in polynomial time?

This problem is not decidable (reducible to halting problem) but is semi-decidable and therefor verifiable (as those two definitions are equivalent: How to prove semi-decidable = verifiable?).

However, is this problem poly-time verifiable? A decision problem 𝑄 is in poly time verifiable iff

there is an algorithm 𝑉 called verifier such that V runs in $ O(x^{c})$ for some constant c for all inputs π‘₯,

if 𝑄(π‘₯)=π‘ŒπΈπ‘† then there is a string 𝑦 such that 𝑉(π‘₯,𝑦)=π‘ŒπΈπ‘†, if 𝑄(π‘₯)=𝑁𝑂 then for all strings 𝑦, 𝑉(π‘₯,𝑦)=𝑁𝑂.

Example: for an enumeration of P (such as this): How does an enumerator for machines for languages work? for each string $ p$ in the enumeration, does there exist some other string (certificate) $ c$ that allows you to verify $ p$ is a member of the enumeration in poly time?

Do all languages in $P$ have polynomial proofs that they are in $P$?

A proof for a language $ L$ belonging to a complexity class $ C$ that is accepted by a mathematical journal can be framed as there existing a verifier $ V$ that accepts this proof as the first part of its input and the language as the second. The verifier (referee) verifies this language is a member (a word) in the language representing the complexity class.

$ Verifier$ : (Proof for $ L$ in $ C$ , $ L$ )$ –>$ [0,1]

Do all languages in $ P$ have a proof of the fact that they are in $ P$ that can be verified in polynomial time? Given a language, determining if an arbitrary $ L$ is in $ P$ or not is undecidable; however, given a proof for a language being in $ P$ , can that language be verified to be in $ P$ in polynomial time?

P=NP when number of input that gives 1 is bounded by polynomial

Suppose there exists some NP-complete problem such that the number of inputs that gives 1 as an output is bounded by a polynomial; that is, if the problem is $ f : \{0, 1 \}^* \to \{0, 1\}$ , then, for every $ n$ , $ |\{ x \in \{0, 1 \}^n : f(x) = 1\}| \leq p(n)$ for some polynomial $ p$ . Then, I want to show that the existence of this problem implies $ P = NP$ . Is it somehow related to LEXSAT?

building a polynomial algorithm that solves SAT when given a polynomial TM that solves SAT on two formulas

Here’s the question:

Assume there exists a polynomial time machine $ M$ that receives two formulas $ \varphi_1,\varphi_2$ and satisfies the following:

  • If $ \varphi_1 \in \mathrm{SAT}$ and $ \varphi_2 \notin \mathrm{SAT}$ , then $ M(\varphi_1,\varphi_2)=1$
  • If $ \varphi_1 \notin \mathrm{SAT}$ and $ \varphi_2 \in \mathrm{SAT}$ , then $ M(\varphi_1,\varphi_2)=0$

Show that there also exists a polynomial time algorithm for SAT.

Note that we have no guarantee for the output of $ M(\varphi_1,\varphi_2)$ whenever $ \varphi_1,\varphi_2$ are both satisfiable (or when both are not).

Can I get any hint on how to start the solution?