# Questions tagged [np]

NP ("nondeterministic polynomial") is a complexity class of decision problems that can be solved by a nondeterministic Turing machine in polynomial time. Equivalently, it is the set of decision problems for which an answer can be verified in polynomial time by a deterministic Turing machine.

**1**

vote

**1**answer

44 views

### Proof of np-completeness

Show that the following problem is NP-complete.
The tv problem is to select tv shows for a weekly tv night so that
everyone in a group of people sees something that they like. You are
given a ...

**-2**

votes

**1**answer

61 views

### How to estimate that this task is in class NP?

Here is my problem: Given numbers x1, ... xn. Numbers meet n files size and memory disk capacity D. We must understand, can we that files divided into 3 disks. The amount of file size recorded on any ...

**0**

votes

**1**answer

11 views

### Please explain how the logic behind defining a new problem as NP-Complete is correct

The logic used goes like this - we have an existing class of problems that are NP-Complete. Now a new problem "Q" comes up.
Step 1 - We prove Q is in NP, well and good.
Step 2 - We show that a ...

**2**

votes

**0**answers

56 views

### A job scheduling problem intending for least total loss

Suppose we have n jobs for scheduling and we want to find a job scheduling order to achieve least total loss. Each job has three properties: (b,l,k) where b indicates the coming time of each job, l ...

**0**

votes

**0**answers

23 views

### What's the difference between the descriptions of “ P can reduce to Q” and “P can be reduced to Q”?

I have just started learning algorithm. But the concept of reduction really makes me confused. Because sometimes we say "P can reduce to Q", but there is also something like " P can be reduced to Q". ...

**0**

votes

**1**answer

50 views

### How to calculate np.mean for images of 3D array?

I want to use mean subtraction and standardization as a normalization for my CNN model. I'm working on Keras classifying images.
However, I don't yet fully understand the difference between using ...

**-1**

votes

**1**answer

33 views

### Prove that the reduction of HAM-CYCLE to TSP is polynomial-time?

This is a question that our professor uploaded yesterday, to prepare for our exam tomorrow. My problem with the question is part b (in boldface below); I'm not sure what I should do exactly.
The ...

**1**

vote

**0**answers

21 views

### np.where not working as expected on new Image

I am working on a morphing project that requires delauney and creating polygons. I have to find where the image is white or black. I know I need to use np.where, however, when I do, it returns an ...

**0**

votes

**0**answers

17 views

### Which NP-complete to pick for a longer path in graph between 2 vertices Problem?

I am given a graph G and problem called LONGER-PATH which looks for a path in G between vertices x and y and returns true if there exists a path with a least k edges. I have to prove that this problem ...

**1**

vote

**1**answer

39 views

### check the existence of value on other Dataframe

I have two data frames F1 and F2 containing both the column id1, id2.
F1 contains two columns F1[id1,id2].
F2 contains three column [id1,id2,Description]
I wante to test if F2['id1']exists in F1['id1'...

**0**

votes

**1**answer

29 views

### In numpy how would be convert values internally

I am new to numpy library.
How values are converted to get below output and internally how the values are changed?
>>> np.convolve([1, 2, 3], [0, 1, 0.5])
o/p: array([ 0. , 1. , 2.5,...

**0**

votes

**1**answer

23 views

### multi-conditional counter based on dates

I have this dataframe
df:
entrance leaving counter
1 2012-07-01 NaT NaN
2 2013-03-15 NaT NaN
3 2013-03-15 2013-04-15 NaN
4 2014-06-01 NaT ...

**0**

votes

**0**answers

61 views

### Exception has occurred: ValueError all the input arrays must have same number of dimensions

What I'm trying to do is take a 250 x 250 px image and turn all the text onto it to 1s and the rest to 0s, then pass this through a neural network. To turn the image to 1s and 0s, I wrote this ...

**-1**

votes

**2**answers

64 views

### Np class of problems

Are All problems in NP are known to be reducible to one another.
I know if a problem X is in NP and any NP problem Y in NP is reducible to X then X is NP-complete. So by this assumption can we state ...

**0**

votes

**1**answer

40 views

### Cook's theorem and NP complete reductions

Based on Cook's theorem,
Any NP problem can be converted to SAT in polynomial time
I know that SAT is a NP-complete problem. Therefore, is it accurate to say:
If we can reduce a search problem A (...

**0**

votes

**1**answer

36 views

### Having trouble understanding the MAX-CUT problem

I'm having trouble understanding the general idea behind the MAX-CUT problem. Consider the graph below.
The MAX-CUT asks us to find the cut that maximizes the number of edges that it touches. I can ...

**1**

vote

**1**answer

71 views

### What approximate TSP algorithm does Google OR-Tools use?

I came across Google OR-Tools which computes the TSP with reasonable approximations as discussed in this link. I am curious to know what specfic algorithm this tool uses for TSP. Does it have any ...

**3**

votes

**3**answers

85 views

### If these problems are NP-Complete, how are there polynomial time algorithms for solving them?

I'm studying P, NP, and NP-Complete problems and I've encountered some questions.
I understand that a problem is P if you can solve it in polynomial time, and a problem is NP if it is verifiable in ...

**0**

votes

**2**answers

45 views

### Merge k unsorted lists into one and sort them and then separate them into k sorted lists?

Say I have k unsorted list and I want to merge them into one list so that I could run my sorting algorithm on them, and then I need to separate this large merged list to get k sorted list. How could I ...

**0**

votes

**1**answer

16 views

### If we can prove that knapsack problem with limited capacity are solved in a polynomial time then all knapsack belongs to P

I found this question in my Optimization Algorithm course, the full question is this:
If we can prove all Knapsack problems with capacity limited to 100 can be solved in polynomial time, then all ...

**0**

votes

**1**answer

26 views

### What is the difference between my own hot_labels and creating hotlabels with functions?

I am new to python and machine learning, since I have been learning day by day. I want to clear somethings, and this time about my labels. I have 2004 classes to classify from. And I am building ...

**-2**

votes

**1**answer

54 views

### What is the best algorithm for travelling sales man problem in case of there is few cites(lower than 6)? [closed]

i have seen many solution that try to solve the problem of travelling salesman problem if p!=np ,but i want to know the optimum solution if there is 6 or 5 cities only,which algorithm will give the ...

**0**

votes

**1**answer

156 views

### Which of the following statements are true for the given special cases of the Traveling Salesman Problem?

I'm taking the Algorithms: Design and Analysis II class, one of the questions asks:
Which of the following statements is true?
Consider a TSP instance in which every edge cost is either 1 ...

**0**

votes

**1**answer

211 views

### Which of the following problems can be reduced to the Hamiltonian path problem?

I'm taking the Algorithms: Design and Analysis II class, one of the questions asks:
Assume that P ≠ NP. Consider undirected graphs with nonnegative edge
lengths. Which of the following problems ...

**1**

vote

**1**answer

75 views

### Example of longest path problem having a NP complexity?

I saw on the internet that finding the longest path problem is NP-Complete problem.
For some reason, my teacher tells me that it isn't an NP-complete problem.
So now I am looking for an example that ...

**0**

votes

**0**answers

47 views

### Given a set of intervals on the number line, find the minimum points that “cover” all the intervals (optimium solution efficiently)?

I've been trying to find an efficient way to solve this problem of finding "minimum" (not minimal) time points, but not sure if it's that straightforward. I tried modeling it as a minimum edge cover ...

**-3**

votes

**1**answer

47 views

### Priority interval scheduling algorithm

I have the following problem.
Imagine a set of jobs, with start time (st) and end time (et). Each job has a priority value. I need to schedule these jobs using a number of machines greater than 1.
...

**0**

votes

**2**answers

100 views

### Algorithm Problem: Find the longest elementary cycle in a directed graph

The problem is: given a directed graph, find the longest simple cycle in the graph. I've searched the question and found this link Finding the longest cycle in a directed graph using DFS. The answer ...

**0**

votes

**1**answer

26 views

### Proof the longest path is NP-Hard with negative edge weights

I know a similar question has been asked before and that there are abundant amount of resources online, but I have a slightly different question. I understand the reduction from HAM Path to Longest ...

**0**

votes

**1**answer

58 views

### What optimization algorithm is more suitable for timetable rescheduling?

I'm working on the project where university course is represented as a to-do list, where:
course owner (teacher of the course) can add tasks (containing the URL to the resource needs to be learned ...

**0**

votes

**0**answers

32 views

### Speed up N(P) problem search - Sum-Square Problem

Speed up N(P) problem search - Sum-Square Problem
I was wondering if anyone could help me figuring out ways to speed up a small programm I was working on.
The problem is a math exercise called the ...

**0**

votes

**1**answer

272 views

### Prove a problem that is NP-hard and not NP-complete in not in P

If A is not NP-hard, but not NP-complete, then prove that A in not in P.
A is NP-hard if there is an NP-complete problem B such that B is reducible to A in polynomial time. A is NP-complete if A ...

**2**

votes

**1**answer

66 views

### I understand 2 SAT can be solved in Polynomial time finding out Strongly Connected Components. What about doing the same for 3SAT?

In case of 3SAT instead of getting 2 implications for one clause, we'd get 12(3C2*2*2) maybe.and which will form a graph of 12m edges when m is the number of clauses in 3 CNF and we can still find out ...

**0**

votes

**0**answers

66 views

### RuntimeWarning: invalid value encountered in double_scalars when solving system of equations

I know this is a recurrent question, but I cannot find the mistake in my code that is generating this error.
I want to solve a system of equations of the following form
System of equations
When I ...

**0**

votes

**0**answers

40 views

### TSP-OPTIMIZE is NP equivalent or strictly NP hard? Looking for a good citation

I'm wondering whether TSP-OPTIMIZE is NP-equivalent, like the proof wiki claims or if it is strictly NP-hard. To clarify, I'm talking about the optimization problem, that is to find the shortest round ...

**-1**

votes

**1**answer

44 views

### Why is the performance of the same loop algorithm differs

Right now I am doing assignments from cs 231 n , and I wanted to calculate euclidean distance between points:
dists[i, j]=0
for k in range(3072):
dists[i, j]+=math.pow((X[i,k] - self.X_train[j,k])...

**0**

votes

**1**answer

96 views

### Issue with creating a column using np.where, ArrayType error

I have a dataframe in which I'm trying to create a binary 1/0 column when certain conditions are met. The code I'm using is as follows:
sd_threshold = 5
df1["signal"] = np.where(np.logical_and(df1["...

**-1**

votes

**1**answer

54 views

### NP, NP-Complete, NP-Hard questions

I am studying NP and I can't understand how can I solve the below questions. I would like to know the strategy that I should use to be able to solve this kind of problems.
The question is:
Assume A ...

**0**

votes

**0**answers

76 views

### Algorithm to avoid obvious costly combinations when splitting n values to m groups

I have 7 values and I need to split them into 5 groups. Each group should contain atleast one value. There are 15 ways to group those values into 5.
Mon- 13
Tue- 5
Wed- 4
Thu- 4
Fri- 11
Sat- 2
Sun- ...

**0**

votes

**1**answer

96 views

### optimal algorithm to solve CLSP(Capacitated Lot Sizing) with the transportation constraints and storage levels

A bank has an ATM machine. For a particular week, the usage of cash in millions as below.
5- Monday
4- Tuesday
1- Wednesday
15- Thursday
6- Friday
2- Saturday
4- Sunday
The bank hires a depositing ...

**0**

votes

**1**answer

24 views

### In complexity class P, accepts=decides. Why not NP?

Suppose some problem L is in the complexity class P. Then there is some polynomial time algorithm A that decides the problem. We have the following theorem: if A accepts L, then A decides L.
The ...

**0**

votes

**0**answers

34 views

### Accepting a Language Vs Rejecting a language

I have a question on complexity theory. I have the following definition in my notes:
If algorithm A is such that A(s) halts with output 1 for all s in language L, then A accepts L.
My question is,...

**0**

votes

**0**answers

18 views

### Finding the best combination of Timeslots in a set

I have the following problem:
I want to find 3 Timeslots in a week that are both:
"nicely distributed" and "have a good quality"
Timeslots are always 1 hour long, so each day of the week has 24 ...

**0**

votes

**1**answer

351 views

### Example in np.argsort document

For some reason I cannot resolve this.
According to the example here for 1-dim array,
https://docs.scipy.org/doc/numpy/reference/generated/numpy.argsort.html
x = np.array([3, 1, 2])
np.argsort(x)
...

**1**

vote

**1**answer

25 views

### NP or Not? Finding a word in an existing dictionary surrounded by Gibberish

So a friend and I have a question which we can't find an answer to.
Given a String of unknown length or size covered in gibberish note the word CAN be misspelled by one or two charachters. Is it ...

**1**

vote

**0**answers

66 views

### Is finding all primes less than n, doable in polynomial time?

Bear in mind I'm almost a complete noob at complexity theory.
I was reading about how AKS Primality shows that numbers of size n can be shown to be prime or composite in polynomial time. Given that, ...

**2**

votes

**0**answers

50 views

### Parallel estimation of multiple nonparametric models using np and snowfall

I am trying to estimate multiple nonparametric models using snowfall. So far I had no problems, but now I run into a problem that I feel unable to resolve.
In the MWE below we simply estimate only ...

**1**

vote

**1**answer

44 views

### What does the word “amortized” mean in amortized analysis of algorithms? [closed]

I obviously am familiar with the texts mentioning it is an average lower bound etc... but still wondering why the word amortized was put there ?
Why is amortize used in describing algorithm analysis ?...

**1**

vote

**1**answer

41 views

### NP to P transition

Are there any recent (feel free to add the "old" ones too) problems that were perceived as NP and then later someone came up with a solution that is Polynomial? I think studying those cases would ...

**0**

votes

**0**answers

28 views

### Reduction from Vertex Cover to Restricted LP

The Restricted LP Problem is as follows:
Given a nn matrix A, a vector b in R^n, and a positive integer k. Does there exists a vector x in R^n with at most k non-zero entries such that Ax is greater ...