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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
2answers
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
1answer
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
1answer
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
1answer
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
3answers
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
2answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
2answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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 ...

http://mssss.yulina-kosm.ru