Skip to main content
deleted 17 characters in body
Source Link

Function Problem that finds the solution

  • Given integer for N.

  • Find 2 integers distinct from N. (But, less than N)

  • That have a product equal to N.

This means we must exclude integers 1 and N.

An algorithm that is pseudo-polynomial

N = 10

numbers = []

for a in range(2, N):
    numbers.append(a)


for j in range(length(numbers)):
  if N/(numbers[j]) in numbers:
   OUTPUT N/(numbers[j]) X numbers[j]
   break

Output

Soltuion Verified: 5 x 2 = N and N=10

The algorithm that solves the Decision Problem

if AKS-primality(N) == False:
 if N != 1:
  OUTPUT YES

Question

Since the decision problem is in P must finding a solution also be solvable in polynomial-time?

Function Problem that finds the solution

  • Given integer for N.

  • Find 2 integers distinct from N. (But, less than N)

  • That have a product equal to N.

This means we must exclude integers 1 and N.

An algorithm that is pseudo-polynomial

N = 10

numbers = []

for a in range(2, N):
    numbers.append(a)


for j in range(length(numbers)):
  if N/(numbers[j]) in numbers:
   OUTPUT N/(numbers[j]) X numbers[j]
   break

Output

Soltuion Verified: 5 x 2 = N and N=10

The algorithm that solves the Decision Problem

if AKS-primality(N) == False:
 if N != 1:
  OUTPUT YES

Question

Since the decision problem is in P must finding a solution also be solvable in polynomial-time?

Function Problem that finds the solution

  • Given integer for N.

  • Find 2 integers distinct from N. (But, less than N)

  • That have a product equal to N.

This means we must exclude integers 1 and N.

An algorithm that is pseudo-polynomial

N = 10

numbers = []

for a in range(2, N):
    numbers.append(a)


for j in range(length(numbers)):
  if N/(numbers[j]) in numbers:
   OUTPUT N/(numbers[j]) X numbers[j]
   break

Output

Soltuion Verified: 5 x 2 = N and N=10

The algorithm that solves the Decision Problem

if AKS-primality(N) == False:
  OUTPUT YES

Question

Since the decision problem is in P must finding a solution also be solvable in polynomial-time?

added 17 characters in body
Source Link

Function Problem that finds the solution

  • Given integer for N.

  • Find 2 integers distinct from N. (But, less than N)

  • That have a product equal to N.

This means we must exclude integers 1 and N.

An algorithm that is pseudo-polynomial

N = 10

numbers = []

for a in range(2, N):
    numbers.append(a)


for j in range(length(numbers)):
  if N/(numbers[j]) in numbers:
   OUTPUT N/(numbers[j]) X numbers[j]
   break

Output

Soltuion Verified: 5 x 2 = N and N=10

The algorithm that solves the Decision Problem

if AKS-primality(N) == False:
 if N != 1:
  OUTPUT YES

Question

Since the decision problem is in P must finding a solution also be solvable in polynomial-time?

Function Problem that finds the solution

  • Given integer for N.

  • Find 2 integers distinct from N. (But, less than N)

  • That have a product equal to N.

This means we must exclude integers 1 and N.

An algorithm that is pseudo-polynomial

N = 10

numbers = []

for a in range(2, N):
    numbers.append(a)


for j in range(length(numbers)):
  if N/(numbers[j]) in numbers:
   OUTPUT N/(numbers[j]) X numbers[j]
   break

Output

Soltuion Verified: 5 x 2 = N and N=10

The algorithm that solves the Decision Problem

if AKS-primality(N) == False:
  OUTPUT YES

Question

Since the decision problem is in P must finding a solution also be solvable in polynomial-time?

Function Problem that finds the solution

  • Given integer for N.

  • Find 2 integers distinct from N. (But, less than N)

  • That have a product equal to N.

This means we must exclude integers 1 and N.

An algorithm that is pseudo-polynomial

N = 10

numbers = []

for a in range(2, N):
    numbers.append(a)


for j in range(length(numbers)):
  if N/(numbers[j]) in numbers:
   OUTPUT N/(numbers[j]) X numbers[j]
   break

Output

Soltuion Verified: 5 x 2 = N and N=10

The algorithm that solves the Decision Problem

if AKS-primality(N) == False:
 if N != 1:
  OUTPUT YES

Question

Since the decision problem is in P must finding a solution also be solvable in polynomial-time?

Source Link

If a decision problem is in P, must finding the solution be possible in polynomial-time?

Function Problem that finds the solution

  • Given integer for N.

  • Find 2 integers distinct from N. (But, less than N)

  • That have a product equal to N.

This means we must exclude integers 1 and N.

An algorithm that is pseudo-polynomial

N = 10

numbers = []

for a in range(2, N):
    numbers.append(a)


for j in range(length(numbers)):
  if N/(numbers[j]) in numbers:
   OUTPUT N/(numbers[j]) X numbers[j]
   break

Output

Soltuion Verified: 5 x 2 = N and N=10

The algorithm that solves the Decision Problem

if AKS-primality(N) == False:
  OUTPUT YES

Question

Since the decision problem is in P must finding a solution also be solvable in polynomial-time?