P vs. NP: Understanding the Most Important Problem in Computer Science

# A simple sorting example
numbers = [64, 34, 25, 12, 22, 11, 90]

# Using Python's built-in sort (Timsort algorithm)
numbers.sort()
print(numbers)  # [11, 12, 22, 25, 34, 64, 90]

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

# Example usage
sorted_list = [1, 3, 5, 7, 9, 11, 13, 15]
result = binary_search(sorted_list, 7)
print(f"Found at index: {result}")  # Found at index: 3

import heapq

def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    pq = [(0, start)]
    
    while pq:
        current_dist, current = heapq.heappop(pq)
        
        if current_dist > distances[current]:
            continue
            
        for neighbor, weight in graph[current].items():
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    
    return distances

# Example: City road network
graph = {
    'A': {'B': 4, 'C': 2},
    'B': {'C': 1, 'D': 5},
    'C': {'D': 8, 'E': 10},
    'D': {'E': 2},
    'E': {}
}

shortest = dijkstra(graph, 'A')
print(shortest)  # {'A': 0, 'B': 4, 'C': 2, 'D': 9, 'E': 11}

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

print(gcd(48, 18))  # 6
print(gcd(1071, 462))  # 21

def verify_sudoku(board):
    """Verify a completed 9x9 Sudoku board - runs in polynomial time"""
    # Check each row
    for row in board:
        if sorted(row) != list(range(1, 10)):
            return False
    
    # Check each column
    for col in range(9):
        column = [board[row][col] for row in range(9)]
        if sorted(column) != list(range(1, 10)):
            return False
    
    # Check each 3x3 box
    for box_row in range(0, 9, 3):
        for box_col in range(0, 9, 3):
            box = []
            for i in range(3):
                for j in range(3):
                    box.append(board[box_row + i][box_col + j])
            if sorted(box) != list(range(1, 10)):
                return False
    
    return True

# Example: Verify a solution
solution = [
    [5,3,4,6,7,8,9,1,2],
    [6,7,2,1,9,5,3,4,8],
    [1,9,8,3,4,2,5,6,7],
    [8,5,9,7,6,1,4,2,3],
    [4,2,6,8,5,3,7,9,1],
    [7,1,3,9,2,4,8,5,6],
    [9,6,1,5,3,7,2,8,4],
    [2,8,7,4,1,9,6,3,5],
    [3,4,5,2,8,6,1,7,9]
]

print(verify_sudoku(solution))  # True - verified in milliseconds

def verify_tsp_solution(cities, route, claimed_distance):
    """Verify a TSP solution - polynomial time"""
    if len(route) != len(cities) or set(route) != set(cities):
        return False
    
    # Calculate total distance
    total = 0
    for i in range(len(route)):
        city_a = route[i]
        city_b = route[(i + 1) % len(route)]
        total += distance(city_a, city_b)
    
    return total == claimed_distance

def distance(city_a, city_b):
    """Calculate distance between two cities"""
    x1, y1 = city_a
    x2, y2 = city_b
    return ((x2 - x1)**2 + (y2 - y1)**2)**0.5

# Example cities (x, y coordinates)
cities = [(0,0), (1,3), (4,3), (6,1), (3,0)]

# Someone claims this is the optimal route with distance 12.9
proposed_route = [(0,0), (3,0), (6,1), (4,3), (1,3)]
claimed_distance = 12.9

# Verification is quick - just add up distances
print(verify_tsp_solution(cities, proposed_route, claimed_distance))

def verify_factorization(n, factors):
    """Verify that factors multiply to n - polynomial time"""
    product = 1
    for factor in factors:
        product *= factor
    return product == n

# Easy to verify
n = 77
factors = [7, 11]
print(verify_factorization(n, factors))  # True

# But finding factors of large numbers is hard
# RSA encryption uses 2048-bit numbers (617 digits)
# Factoring them would take billions of years with current computers

def verify_graph_coloring(graph, coloring, num_colors):
    """Verify a graph coloring is valid - polynomial time"""
    # Check we're using the right number of colors
    if max(coloring.values()) >= num_colors:
        return False
    
    # Check no adjacent nodes have the same color
    for node, neighbors in graph.items():
        for neighbor in neighbors:
            if coloring[node] == coloring[neighbor]:
                return False
    
    return True

# Example: Can we color this map with 3 colors?
map_graph = {
    'A': ['B', 'C', 'D'],
    'B': ['A', 'C'],
    'C': ['A', 'B', 'D'],
    'D': ['A', 'C']
}

proposed_coloring = {'A': 0, 'B': 1, 'C': 2, 'D': 1}
print(verify_graph_coloring(map_graph, proposed_coloring, 3))  # True

def verify_sat(formula, assignment):
    """Verify a boolean formula is satisfied - polynomial time"""
    # Example formula: (A OR B) AND (NOT A OR C) AND (NOT B OR NOT C)
    clause1 = assignment['A'] or assignment['B']
    clause2 = (not assignment['A']) or assignment['C']
    clause3 = (not assignment['B']) or (not assignment['C'])
    
    return clause1 and clause2 and clause3

# Verify this assignment satisfies the formula
assignment = {'A': True, 'B': False, 'C': True}
print(verify_sat(None, assignment))  # True

# Simplified RSA concept
def rsa_encrypt(message, public_key):
    """Encryption is fast (polynomial time)"""
    e, n = public_key
    return pow(message, e, n)

def rsa_decrypt(ciphertext, private_key):
    """Decryption is fast IF you have the private key"""
    d, n = private_key
    return pow(ciphertext, d, n)

# The security relies on factoring being hard
# Public key: (e=17, n=3233)  where n = 61 × 53
# Private key: (d=2753, n=3233)

message = 123
public = (17, 3233)
private = (2753, 3233)

encrypted = rsa_encrypt(message, public)
print(f"Encrypted: {encrypted}")  # Fast

decrypted = rsa_decrypt(encrypted, private)
print(f"Decrypted: {decrypted}")  # Fast with key

# But finding the private key from the public key
# requires factoring n = 61 × 53
# For real RSA (2048-bit numbers), this is believed impossible

def solve_sat_bruteforce(num_variables):
    """Try all possible assignments - exponential time!"""
    # For n variables, there are 2^n possible assignments
    for i in range(2**num_variables):
        assignment = {}
        for var in range(num_variables):
            assignment[f'x{var}'] = bool((i >> var) & 1)
        
        if check_formula(assignment):
            return assignment
    return None

# For just 100 variables, there are 2^100 possibilities
# That's more than the number of atoms in the universe!

def knapsack_bruteforce(items, capacity):
    """Try all combinations - exponential time"""
    n = len(items)
    best_value = 0
    best_combo = []
    
    # Try all 2^n combinations
    for i in range(2**n):
        combo = []
        total_weight = 0
        total_value = 0
        
        for j in range(n):
            if (i >> j) & 1:
                combo.append(items[j])
                total_weight += items[j]['weight']
                total_value += items[j]['value']
        
        if total_weight <= capacity and total_value > best_value:
            best_value = total_value
            best_combo = combo
    
    return best_combo, best_value

# Example: Pack a backpack optimally
items = [
    {'name': 'laptop', 'weight': 5, 'value': 1000},
    {'name': 'camera', 'weight': 2, 'value': 500},
    {'name': 'book', 'weight': 1, 'value': 50},
    {'name': 'water', 'weight': 2, 'value': 20}
]

best, value = knapsack_bruteforce(items, 7)
print(f"Best value: {value}")  # Takes 2^4 = 16 iterations
# With 50 items? 2^50 = 1 quadrillion iterations

def graph_coloring_bruteforce(graph, num_colors):
    """Try all possible colorings - exponential time"""
    nodes = list(graph.keys())
    n = len(nodes)
    
    # Try all num_colors^n possible colorings
    for coloring_num in range(num_colors**n):
        coloring = {}
        temp = coloring_num
        
        for node in nodes:
            coloring[node] = temp % num_colors
            temp //= num_colors
        
        if is_valid_coloring(graph, coloring):
            return coloring
    
    return None

def is_valid_coloring(graph, coloring):
    """Check if coloring is valid"""
    for node, neighbors in graph.items():
        for neighbor in neighbors:
            if coloring[node] == coloring[neighbor]:
                return False
    return True

# Real-world use: Exam scheduling
# Each course is a node, edges connect courses with shared students
# Colors represent time slots
# Finding minimum colors needed is NP-complete

from itertools import permutations

def tsp_bruteforce(cities):
    """Try all possible routes - exponential time"""
    n = len(cities)
    min_distance = float('inf')
    best_route = None
    
    # Try all (n-1)! possible routes
    for perm in permutations(cities[1:]):
        route = [cities[0]] + list(perm)
        dist = calculate_route_distance(route)
        
        if dist < min_distance:
            min_distance = dist
            best_route = route
    
    return best_route, min_distance

def calculate_route_distance(route):
    """Calculate total distance of a route"""
    total = 0
    for i in range(len(route)):
        total += distance(route[i], route[(i+1) % len(route)])
    return total

# For 10 cities: 9! = 362,880 routes
# For 20 cities: 19! = 121,645,100,408,832,000 routes
# For 50 cities: More routes than atoms in the universe

# Hypothetical scenario
def magic_sat_solver(formula):
    """Imagine we found a polynomial-time SAT solver"""
    # This would be revolutionary!
    pass

# We could then solve ALL NP-complete problems quickly:
# - TSP: Reduce to SAT, solve with magic_sat_solver
# - Knapsack: Reduce to SAT, solve with magic_sat_solver
# - Graph Coloring: Reduce to SAT, solve with magic_sat_solver
# - And thousands more...

def tsp_nearest_neighbor(cities):
    """Greedy approximation - polynomial time, not optimal"""
    unvisited = set(cities[1:])
    route = [cities[0]]
    current = cities[0]
    
    while unvisited:
        # Pick nearest unvisited city
        nearest = min(unvisited, key=lambda city: distance(current, city))
        route.append(nearest)
        unvisited.remove(nearest)
        current = nearest
    
    return route

# This runs in O(n²) time - fast!
# But the solution might be 25% longer than optimal
# For real-world logistics, that's often good enough

def will_it_halt(program, input_data):
    """Can we determine if a program will halt?"""
    # This function is IMPOSSIBLE to write correctly!
    # Alan Turing proved this in 1936
    pass

# Example programs
def program1(n):
    """This halts"""
    return n + 1

def program2(n):
    """This loops forever"""
    while True:
        n += 1

# We can't write a general algorithm that determines
# whether ANY program will halt on ANY input

def find_best_chess_move(board_state):
    """Find the optimal move - NP-hard"""
    # Would need to explore all possible future games
    # Chess has ~10^120 possible games
    # More than atoms in the universe
    
    # Even verifying a move is "optimal" is hard
    # You'd need to check all alternatives
    pass

# This is why chess engines use:
# - Heuristics (position evaluation)
# - Pruning (alpha-beta)
# - Time limits
# They don't find optimal moves, just good ones

# NP-complete (decision): "Is there a tour shorter than K?"
def tsp_decision(cities, max_distance):
    """Can we visit all cities in distance <= max_distance?"""
    # This is NP-complete (yes/no answer)
    pass

# NP-hard (optimization): "What's the shortest tour?"
def tsp_optimization(cities):
    """Find the absolute shortest tour"""
    # This is NP-hard (finding the best value)
    # Harder because you need to find the minimum,
    # not just check if a solution exists
    pass

# Protein folding - predicting 3D structure
def predict_protein_structure(amino_acid_sequence):
    """NP-hard - critical for drug discovery"""
    # Billions spent on this problem
    # AlphaFold uses AI approximations
    pass

# Circuit design optimization
def optimize_circuit_layout(components, connections):
    """NP-hard - chip manufacturing"""
    # Intel, AMD, NVIDIA face this daily
    pass

# Resource allocation
def optimal_resource_allocation(tasks, resources, constraints):
    """NP-hard - cloud computing, manufacturing"""
    # AWS, Google Cloud use approximations
    pass

# Modern encryption relies on hard problems
def secure_communication():
    """How your data stays safe"""
    
    # RSA: Based on integer factorization (NP problem)
    # Breaking it requires factoring large numbers
    # Example: n = 2^2048 (617-digit number)
    # Estimated time to factor: billions of years
    
    # Elliptic Curve Cryptography: Based on discrete log
    # Also believed to be hard (NP-like problem)
    
    # If P = NP:
    # - All encryption breaks
    # - No secure online banking
    # - No private communications
    # - Digital signatures become forgeable
    pass

# UPS/FedEx delivery routing
def optimize_delivery_routes(packages, trucks, destinations):
    """Save millions in fuel costs"""
    # This is TSP - NP-complete
    # UPS saves $50M/year with better approximations
    # Even 1% improvement = huge savings
    pass

# Airline scheduling
def optimize_flight_schedules(planes, routes, crews):
    """Maximize profit, minimize delays"""
    # NP-complete problem
    # Airlines use sophisticated heuristics
    # Better solutions = millions saved
    pass

# Manufacturing scheduling
def optimize_production(machines, orders, deadlines):
    """Minimize downtime, meet deadlines"""
    # Job shop scheduling - NP-complete
    # Toyota, Tesla face this daily
    pass

# Game AI
def find_best_strategy(game_state):
    """Chess, Go, poker strategy"""
    # Optimal play is NP-hard
    # AlphaGo uses neural networks + search
    # Approximates, doesn't solve optimally
    pass

# Planning and scheduling
def plan_robot_actions(start, goal, obstacles):
    """Robot path planning"""
    # Often NP-complete
    # Self-driving cars use approximations
    pass

# Machine learning optimization
def train_neural_network(data, architecture):
    """Find optimal weights"""
    # Non-convex optimization - NP-hard
    # We use gradient descent (local optimum)
    # Not guaranteed to find global optimum
    pass

# Protein folding
def predict_protein_fold(amino_acids):
    """Predict 3D structure from sequence"""
    # NP-hard problem
    # Critical for understanding diseases
    # AlphaFold uses AI approximations
    # Breakthrough, but not optimal solution
    pass

# Drug design
def find_optimal_drug(target_protein):
    """Search chemical space for best molecule"""
    # Chemical space: 10^60 possible molecules
    # NP-hard to search optimally
    # Pharma companies use heuristics
    # Better algorithms = faster cures
    pass

# This is NP (verifiable quickly)
def is_np_problem(problem):
    return can_verify_solution_quickly(problem)

# NOT "can't solve in polynomial time"
# Some NP problems ARE in P!

# We solve NP-complete problems every day!
def practical_tsp_solver(cities):
    """Not optimal, but good enough"""
    # Nearest neighbor: O(n²) time
    # Solution within 25% of optimal
    # Good enough for real delivery routes
    pass