P ,NP , NP-Complete , NP-hard

I assume that you are looking for intuitive definitions, since the technical definitions require quite some time to understand. First of all, let's remember a preliminary needed concept to understand those definitions.

• Decision problem: A problem with a yes or no answer.

---

Now, let us define those complexity classes.

P

P is a complexity class that represents the set of all decision problems that can be solved in polynomial time. That is, given an instance of the problem, the answer yes or no can be decided in polynomial time.

Example

Given a connected graph G, can its vertices be coloured using two colours so that no edge is monochromatic?

Algorithm: start with an arbitrary vertex, color it red and all of its neighbours blue and continue. Stop when you run out of vertices or you are forced to make an edge have both of its endpoints be the same color.

---

NP

NP is a complexity class that represents the set of all decision problems for which the instances where the answer is "yes" have proofs that can be verified in polynomial time.

This means that if someone gives us an instance of the problem and a certificate (sometimes called a witness) to the answer being yes, we can check that it is correct in polynomial time.

Example

Integer factorisation is in NP. This is the problem that given integers n and m, is there an integer f with 1 < f < m, such that f divides n (f is a small factor of n)?

This is a decision problem because the answers are yes or no. If someone hands us an instance of the problem (so they hand us integers n and m) and an integer f with 1 < f < m, and claim that f is a factor of n (the certificate), we can check the answer in polynomial time by performing the division n / f.

---

NP-Complete

NP-Complete is a complexity class which represents the set of all problems X in NP for which it is possible to reduce any other NP problem Y to X in polynomial time.

Intuitively this means that we can solve Y quickly if we know how to solve X quickly. Precisely, Yis reducible to X, if there is a polynomial time algorithm f to transform instances y of Y to instances x = f(y) of X in polynomial time, with the property that the answer to y is yes, if and only if the answer to f(y) is yes.

Example

3-SAT. This is the problem wherein we are given a conjunction (ANDs) of 3-clause disjunctions (ORs), statements of the form

(x_v11 OR x_v21 OR x_v31) AND 
(x_v12 OR x_v22 OR x_v32) AND 
...                       AND 
(x_v1n OR x_v2n OR x_v3n)

where each x_vij is a boolean variable or the negation of a variable from a finite predefined list (x_1, x_2, ... x_n).

It can be shown that every NP problem can be reduced to 3-SAT. The proof of this is technical and requires use of the technical definition of NP (based on non-deterministic Turing machines). This is known as Cook's theorem.

What makes NP-complete problems important is that if a deterministic polynomial time algorithm can be found to solve one of them, every NP problem is solvable in polynomial time (one problem to rule them all).

---

NP-hard

Intuitively, these are the problems that are at least as hard as the NP-complete problems. Note that NP-hard problems do not have to be in NP, and they do not have to be decision problems.

The precise definition here is that a problem X is NP-hard, if there is an NP-complete problem Y, such that Y is reducible to X in polynomial time.

But since any NP-complete problem can be reduced to any other NP-complete problem in polynomial time, all NP-complete problems can be reduced to any NP-hard problem in polynomial time. Then, if there is a solution to one NP-hard problem in polynomial time, there is a solution to all NP problems in polynomial time.

Example

The halting problem is an NP-hard problem. This is the problem that given a program P and input I, will it halt? This is a decision problem but it is not in NP. It is clear that any NP-complete problem can be reduced to this one. As another example, any NP-complete problem is NP-hard.

My favorite NP-complete problem is the Minesweeper problem.

---

P = NP

This one is the most famous problem in computer science, and one of the most important outstanding questions in the mathematical sciences. In fact, the Clay Institute is offering one million dollars for a solution to the problem (Stephen Cook's writeup on the Clay website is quite good).

It's clear that P is a subset of NP. The open question is whether or not NP problems have deterministic polynomial time solutions. It is largely believed that they do not. Here is an outstanding recent article on the latest (and the importance) of the P = NP problem

Sample JDBC Connection Example JAVA,JDBC,MYSQL

/**
 * 
 */
package DatabaseConnection;

import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.SQLException;
import java.util.Properties;


/**
 * @author satyanarayanagokavarapu
 *
 */
public class MySqlConnectionExample {

 /**
  * @param args
  */
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  // creates three different Connection objects
  Connection conn2 = null;

  try {

   String url2 = "jdbc:mysql://localhost:3306/soccer?
   user=root&password=mysql123";
   conn2 = DriverManager.getConnection(url2);
   if (conn2 != null) {
    System.out.println("Connected to the database soccer");
   }
  } catch (SQLException ex) {
   System.out.println("An error occurred. Maybe user/password is
 invalid");
   ex.printStackTrace();
  }
 }

}

MYSQL - SELECT Database

1. Open your terminal. 

2. Connect to MySql.If not use below link to know how to connect.

How to Connect to MySql Database using MAC terminal

3. Once you logged into your mysql then type the below command 
to SELECT a database (OMS is database name).
mysql> use OMS;
Database changed;

Which says Database 'OMS' is selected.

4. To check whether Database OMS selected or not type below 
command.
mysql> SELECT DATABASE();
+------------+
| DATABASE() |
+------------+
| oms        |
+------------+
1 row in set (0.00 sec)

Which says Database 'OMS' is selected.

***********Happy Learning*************

MYSQL - Drop Database

1. Open your terminal. 

2. Connect to MySql.If not use below link to know how to connect.

How to Connect to MySql Database using MAC terminal

3. Once you logged into your mysql then type the below command 
to drop a database (OMS is database name).
mysql> drop DATABASE OMS;


4. To check whether Database OMS dropped or not type below 
command.
mysql> USE OMS;
ERROR 1049 (42000): Unknown database 'oms'

Which says Database 'OMS' no more exits.

***********Happy Learning*************

MYSQL - Create Database

1. Open your terminal. 

2. Connect to MySql.If not use below link to know how to connect.

How to Connect to MySql Database using MAC terminal

3. Once you logged into your mysql then type the below command 
to create a database.
mysql> CREATE DATABASE OMS;
Query OK, 1 row affected (0.00 sec)   
1 row affected means Database is created successfully.

4. To use this Database OMS type below command.
mysql> USE OMS;
Database changed

5. Check which database you are using by using below command.
mysql> SELECT DATABASE();
+------------+
| DATABASE() |
+------------+
| oms        |
+------------+
1 row in set (0.00 sec)


***********Happy Learning*************

How to Connect to MySql Database using MAC terminal

1. Open your terminal. 

2. Check your current directory by typing pwd.
$ pwd

Output :
/usr/local/mysql/bin
your directory should be the bin folder of mysql else go to that 
directory by typing.
$ cd /usr/local/mysql/bin


3. When you are in mysql bin folder login to your mysql database 
using below command and enter password.
$ ./mysql -u root -p
Enter password: 
Output :

Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 93
Server version: 5.7.19 MySQL Community Server (GPL)

Copyright (c) 2000, 2017, Oracle and/or its affiliates. 
All rights reserved.

Oracle is a registered trademark of Oracle Corporation and/or its
affiliates. Other names may be trademarks of their respective
owners.

Type 'help;' or '\h' for help. Type '\c' to clear the current input 
statement.

mysql>    

If you see above welcome message then you are logged in to your mysql database.

Java - JDBC Connection Example-1.

Problem Description
How to connect to a database using JDBC?

Assume that database name is OMS(OrderManagementSystem) and it has table named orders which has 5 records.

JAVA INSTALLATION ON MAC

1. Download the Java from Oracle official site.
2. You can download from here : Oracle Site
3. Double click on the file that is downloaded to launch it.
4. Double click on the package icon to launch install Wizard.
5. Click Next and Finish.

Basic Enum EXAMPLE

An enum type is a special data type that enables for a variable to be a set of predefined constants and the names of an enum type's fields are in uppercase letters.

In the Java programming language, you define an enum type by using the enum keyword.

Project Structure

OrderStatus.java

Test.java

OUTPUT

Download SourceCode From Github

ClickToDownload

Get our Articles via Email. Enter your email address.

SWAGGER 2 CONFIGURATION IN AN EXISTING SPRING REST API

How to change Maven resources folder location ?

Maven resources folder contains all your project related xml files , images , text files.

If you want to change the default location from "yourproject/src/main/resources" to your required one or you want to add a new resource folder as per your project needs.

Follow below steps.

Go to your project pom.xml file and search for resources tag and add the new resource folder location with resource tag as below.

For example :

<!-- POM File -->
<resources>
<----------Old resource folder-----------------!>
<resource>
 <directory>src/main/resources</directory>
</resource>
<----------New resource folder-----------------!>
<resource>
 <directory>src/main/Yourrequiredfoldername</directory>
</resource>
<-----------------------------------------------!>
</resources>

Hope this is helpful..........!!!!Thank You.

How to Search Maven Coordinates or Dependecy details-POM.XML

If you want to add a dependency in your maven project , you should know the dependency details to add in POM.XML file of your project.

Then here where we will get stuck usually . We just know which jar or dependency is required that to be added , but we don't know the dependency details.

For any dependency to be added in your POM.XML file we should following three values.

1. GroupId (Package name)
2. ArtifactId (Dependency name)
3. Version (Dependency Version)

You can know the above details by visiting maven central repository site.

Click here : Search in Maven Central Repository

Just type your dependency name , you will get a list of related dependencies with different versions.

You can see the GroupId , Artifact Id and version details .

Click on your required thing and download it and add dependency details in your POM.XML

For example :

For log4j :
<!-- Log4j details -->
<dependency>
 <groupId>org.apache.logging.log4j</groupId>
 <artifactId>log4j</artifactId>
 <version>2.8.2</version>
</dependency>

Search results for log4j in central repository.



Click on version to more details as below.

In similar way search any dependency you needed in central repository and add in your pom.xml . maven will download it and will keep it in your local repository.

Hope this is helpful..........!!!!Thank You.

JAVA CODE SNIPPET-7

/**
 * 
 */
package techyield;

/**
 * @author satyanarayana gokavarapu
 *
 */
public class Super {
 void init( long a,long b)
 {
  System.out.println("Super class long,long method.");
 }
 void init( Long a,Long b)
 {
  System.out.println("Super class Long,Long method.");
 }
}

package techyield;
/**
 * @author satyanarayana gokavarapu
 *
 */
public class Test extends Super{

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  Super object = new Test();
  object.init(2,3);
 }
 void init( int a,int b)
 {
  System.out.println("Test class int,int method.");
 }
 void init(int... a)
 {
  System.out.println("Test class varargs method.");
 }
 void init( long a,long b)
 {
  System.out.println("Test class long,long method.");
 }
}

Select an answer

Test class varargs method.

Test class long,long method.

Super class Long,Long method.

Super class long,long method.
Compile Time Error.
Test class int,int method.

Please comment below if you have any doubts.

JAVA CODE SNIPPET-10

/**
 * 
 */
package techyield;

/**
 * @author satyanarayana gokavarapu
 *
 */
public class Node {

 public Node(int i) {
  System.out.println("In Node class parameterized constructor "+i);
 }

}

package techyield;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author satyanarayana gokavarapu
 *
 */
public class Test{

 public static void main(String[] args) {
  // TODO Auto-generated method stub

  List list = new ArrayList();
  list.add(new Node(10));
  list.add(new String("Krishna"));
  System.out.println(list.get(1)); 

  Set set = new HashSet();
  set.add(new Node(1));
  set.add(new Node(2));
  set.add(new Node(2));
  System.out.println("Length of set is "+set.size());
 }


}

Select an answer

Compile Time Error

Runtime Exception can't insert duplicates into set.

In Node class parameterized constructor 10
Krishna
In Node class parameterized constructor 1
In Node class parameterized constructor 2
In Node class parameterized constructor 2
Length of set is 3

In Node class parameterized constructor 10
Krishna
In Node class parameterized constructor 1
In Node class parameterized constructor 2
In Node class parameterized constructor 2
Length of set is 2

Please comment below if you have any doubts.

JAVA CODE SNIPPET-9

package techyield;
/**
 * @author satyanarayana gokavarapu
 *
 */
public class Test{

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  Test object = new Test();
  int value=4;
  object.init(value,value);
 }
 void init( Long a,Long b)
 {
  System.out.println("Test class Long,Long method.");
 }
 void init(int... a)
 {
  System.out.println("Test class varargs method.");
 }
}

Select an answer

Compilation Error.

Test class Long,Long method.

No Output.

Test class varargs method.

Please comment below if you have any doubts.

JAVA CODE SNIPPET-8

package techyield;
/**
 * @author satyanarayana gokavarapu
 *
 */
public class Test{

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  Test object = new Test();
  int value=4;
  object.init(value,value);
 }
 void init( Long a,Long b)
 {
  System.out.println("Test class Long,Long method.");
 }
 void init(int... a)
 {
  System.out.println("Test class varargs method.");
 }
 void init( long a,long b)
 {
  System.out.println("Test class long,long method.");
 }
}

Select an answer

Compilation Error.

Test class Long,Long method.

Test class long,long method.

Test class varargs method.

Please comment below if you have any doubts.

JAVA CODE SNIPPET-6

/**
 * 
 */
package techyield;

/**
 * @author satyanarayana gokavarapu
 *
 */
public class Super {
 void init( long a,long b)
 {
  System.out.println("Super class long,long method.");
 }
 void init( Long a,Long b)
 {
  System.out.println("Super class Long,Long method.");
 }
}

package techyield;
/**
 * @author satyanarayana gokavarapu
 *
 */
public class Test extends Super{

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  Super object = new Test();
  object.init(2,3);
 }
 void init( int a,int b)
 {
  System.out.println("Test class int,int method.");
 }
 void init(int... a)
 {
  System.out.println("Test class varargs method.");
 }
}

Select an answer

Test class varargs method.

No output.

Super class Long,Long method.

Super class long,long method.
Compile Time Error.
Test class int,int method.

Please comment below if you have any doubts.

JAVA CODE SNIPPET-5

/**
 * 
 */
package techyield;

/**
 * @author satyanarayana gokavarapu
 *
 */
public class Super {
 void init( int a,int b)
 {
  System.out.println("Super class int,int method.");
 }
 void init( long a,long b)
 {
  System.out.println("Super class long,long method.");
 }
 void init( Long a,Long b)
 {
  System.out.println("Super class Long,Long method.");
 }
}

package techyield;
/**
 * @author satyanarayana gokavarapu
 *
 */
public class Test extends Super{

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  Test object = new Test();
  object.init(2,3);
 }
 void init(int... a)
 {
  System.out.println("Test class varargs method.");
 }
}

Select an answer

Test class varargs method.

Super class int,int method.

Super class Long,Long method.

Super class long,long method.

Please comment below if you have any doubts.

JAVA CODE SNIPPET-4

/**
 * 
 */
package techyield;

/**
 * @author satyanarayana gokavarapu
 *
 */
public class Super {
 void init(final long a,long b)
 {
  System.out.println("Super class long method.");
 }

}

package techyield;
/**
 * @author satyanarayana gokavarapu
 *
 */
public class Test extends Super{

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  Test object = new Test();
  object.init(2,3);
 }
 void init(int... a)
 {
  System.out.println("Test class varargs method.");
 }
}

Select an answer

Compile Time error

Super class long method.

Test class varargs method.

Run Time exception.

Please comment below if you have any doubts.

JAVA CODE SNIPPET-3

public class Techyield {


 private static int p = test();

 static int test()
 {
  return 99;
 }


 public static void main(String[] args) {
  // TODO Auto-generated method stub
  System.out.println("value of p"+p);
  System.out.println(++p);
  System.out.println(5+p--+2);
  System.out.println(++p*10);
 }

}

Select an answer

Static variable should be called with class name.

value of p is 99
100
106
1070

value of p is 99
100
107
1070

value of p is 99
100
107
1000

value of p is 99
100
107
1080

Please comment below if you have any doubts.

JAVA CODE SNIPPET-2

public class Techyield {


 private static int p = test();

 static int test()
 {
  return 99;
 }


 public static void main(String[] args) {
  // TODO Auto-generated method stub
  System.out.println("Value of p is "+p);
 }

}

Select an answer

Static variable should be called with class name.

Compile time error

Value of p is 99

Program will compile but no output.

Please comment below if you have any doubts.

JAVA CODE SNIPPET-1

package techyield;

public class GrandParent {
 public void method1(int a){
  System.out.println("In GrandParent class and in method1 
and with one int argument and value is "+a);
 }
}

package techyield;

public class Parent extends GrandParent{
 public void method1(int a){
  System.out.println("In Parent class and in method1 and 
with one int argument and value is "+a);
 }
}

package techyield;

public class Child extends Parent{

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  System.out.println("Main method");
  Child child=new Child();
  child.method1(2);

 }
 public void method1(int a){
  System.out.println("In child class and in method1 and 
with one int argument and value is "+a);
 }
}

What is the Output On the Console ?

Select an answer

Main method
In child class and in method1 and with one int argument and value is 2


Main method
In Parent class and in method1 and with one int argument and value is 2

Main method
In GrandParent class and in method1 and with one int argument and value 
is 2


Compile Time error

Please comment below if you have any doubts.

Educational Documents for F1 Visa

Educational Documents for F1 Visa

• Original degree certificates along with mark sheets.

In case if you didn't received your original degree certificate or if you just completed final year take your mark sheets and provisional certificate if available. 

Sometimes immigrant officer may even say ,  to attend interview after getting documents with out rejecting.

• Original bachelor degree transcripts or high school diploma along with  mark sheets all the previous institutions you attended.
• Test scores GRE , TOEFL or IELTS or SAT , GMAT , LSAT . Take all those exam related documents on what basis you got admitted into the University or School or College.
• Some Universities may not require scores , in that case you have to show the proof that University doesn't require such scores . 

For example : Showing a letter from University that it doesn't require particular exam score for the admission.

Note : Having good scores in exams always have good impact or impression during F1 Visa.

Useful Links :

Documents Checklist for F1 Visa (Student Visa)

Financial Documents for F1 Visa

Educational Documents for F1 Visa

F1 Visa Interview Questions

List of items you need to carry while travelling to USA

Financial Documents for F1 Visa

Financial Documents for F1 Visa

An F1 visa applicant need to show evidence of financial resources, proof of liquid assets sufficient to pay for the entire first year of education and living expenses and also proof of readily available funds to cover the remaining year(s) of studies.

Proof of your Financial resources or documents should be of following category :

• Applicant's personal resources . By showing bank statements either liquid amount , assests , house , land , agricultural lands or Fixed Deposits.
• Pay slips , PF , Employment letters.
• Chartered account statement if available not mandatory.
• Tax returns of the past 3 years (Form 16) .
•  In case if someone is sponsoring you , then you have to carry his tax returns of past 3 years ,  his bank statement showing sufficient funds .
• In case if your sponsor is in US . Then you have to carry a notarized FORM I-134 along with his past 3 years tax returns and bank statement.(It is not better to show assets of persons in the United States).
• Financial aid from the university in the form of a scholarship, fellowship, assistant-ship (TA/GA/RA). which will be mentioned in your I-20 .
• Financial aid from the student's home government if your government is sponsoring for your studies or any private organizations sponsoring you.

Note : Always answer to immigrant officer with confidence , if any transactions done in your bank account recently answer correctly, why those transactions happened . Be ready with answers don't panic .

Useful Links :

Documents Checklist for F1 Visa (Student Visa)

Financial Documents for F1 Visa

Educational Documents for F1 Visa

F1 Visa Interview Questions

List of items you need to carry while travelling to USA

Documents Checklist for F1 Visa (Student Visa)

Mandatory Documents

• Current passport . If you have old passports please carry them too
• Carry copies of first page , last page and remarks page of your current passport.
• One photograph
• Confirmation page of online submitted DS-160 Form with CEAC bar code.
• Visa Fees paid receipt. You have to pay the Visa Fees before attending for the interview .
• Original interview appointment letter and one copy of it.
• (I-901) SEVIS Fee paid receipt and one copy of it.
• Both pages of bar-coded original SEVIS generated Form I-20 which you received from the US School ,College or University that you are going . Take a copy of it .(Xerox copy of I-20)

Note : The original Form I-20 must be signed by you and by the school official.

           You may get many I-20's from many universities that you applied but make
           sure that you are showing  the right one to the authority.
           Even if you carry all I-20's .

           During F1 Visa interview they will never stamp on your I-20 . Once when you
           enter US the immigrant officer at the entry will stamp on it.

• Evidence of financial resouces. so carry your Financial Documents.
• Educational Documents. so carry your Educational Documents .

Useful Links :

Documents Checklist for F1 Visa (Student Visa)

Financial Documents for F1 Visa

Educational Documents for F1 Visa

F1 Visa Interview Questions

List of items you need to carry while travelling to USA

Petrol Pump solution Mettl.

Question :


A petrol tank has infinite capacity it can store infinite litres of petrol .

There are Four petrolpumps say 1 , 2 , 3 , 4. which are in circular manner.

PetrolTank should start from one petrol pump and should reach other petrolpump and should complete the circle with out any break.

Given input is a two dimensional array first column is petrol capacity of petrolpump and second column is distance to next petrol pump.

If petroltank can start from two petrol pumps means then you should start from least petrol pump number.

Given input array is int [][] array1 ={{3,3},
                            {7,4},
                            {7,8},
                            {9,8}}

For this input petrol tank can start from petrolpump 2 and petrolpump 4 but as we have to start from least number of petrolpump it will start from petrolpump 2 and will finish the circle.

Hints : You have to check whether input is two dimensional array or not .


Solution :

PetrolProblem.java

/**
 * 
 */
package com.techyield.blogspot.in;

/**
 * @author SATYA
 *
 */
public class PetrolProblem {


public int startPointofPetrolTank(int [][] input){
int petrolPumpnumber=0;
try{
int row= input.length;
int totaldistance=0;
int totalpetrol=0;
for(int i=0;i<row;i++){
int col=input[i].length;
if(col!=2){
throw new UnsupportedException("Input is not a two dimentional array.");
}
}
for(int i =0; i<row;i++){
totaldistance+=input[i][1];
totalpetrol+=input[i][0];
}
if(totalpetrol<totaldistance){
return 0;
}
for(int i =0; i<row;i++){
if(input[i][0]>input[i][1]){
petrolPumpnumber=i+1;
break;
}
}

}
catch(UnsupportedException e){
System.out.println(e.getMessage());
}
catch(Exception e){
System.out.println(e.getMessage());
}
return petrolPumpnumber;
}

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

int [][] array1 ={{3,3},
{7,4},
{7,8},
{9,8}
};
PetrolProblem object = new PetrolProblem();
int petrolPumpindex =object.startPointofPetrolTank(array1);
if(petrolPumpindex >=1)
System.out.println("Petrol Tank will start from PetrolPump "+petrolPumpindex+"");
else
System.out.println("PetrolTank can't start from any petrol pump");
}

}

UnsupportedException.java


package com.techyield.blogspot.in;

public class UnsupportedException extends Exception {

public UnsupportedException(String s){
super(s);
}

}

Output :

Petrol Tank will start from PetrolPump 2