Spaces:
Sleeping
Sleeping
from google import genai | |
from google.genai import types | |
import gradio as gr | |
import os | |
MODEL_ID = "gemini-2.0-flash-thinking-exp" | |
from google import genai | |
client = genai.Client(api_key=os.getenv('api_key')) | |
def llm_response(text): | |
response = client.models.generate_content( | |
model=MODEL_ID, | |
contents= text) | |
return response.text | |
def pvsnp(problem): | |
classification = llm_response(f''' | |
You are an expert in computational complexity theory, specializing in both classical complexity classes (P, NP, NP-complete, NP-hard) and modern developments (e.g., parameterized complexity, fine-grained complexity, Minimum Circuit Size Problem). | |
Your task is to classify a given problem into one of the following categories: | |
P: Solvable in deterministic polynomial time. | |
NP: Verifiable in polynomial time. | |
NP-complete: Both in NP and NP-hard. | |
NP-hard: At least as hard as NP-complete problems, possibly outside NP. | |
Beyond NP: Likely in PSPACE, EXPTIME, or undecidable. | |
Other: Fits alternative complexity classes (e.g., BPP, co-NP). | |
Problem Description: | |
{problem} | |
If the given problem is a NP-hard problem, decompose the NP-hard problem into polynomial-time solvable subproblems without solving them. | |
🔹 Inputs: | |
A formal definition and instance of the NP-hard problem (e.g., SAT, TSP, Graph Coloring). | |
Optional: Constraints or domain knowledge. | |
🔹 Decomposition Process: | |
Graph Representation & Structural Analysis | |
Convert the problem into a graph (if applicable). | |
Identify independent or tractable substructures. | |
Classification of Subproblems | |
Detect polynomially solvable parts (e.g., tree structures, bipartite graphs). | |
Separate them from harder components. | |
Partitioning & Transformation | |
Break the problem into independent or loosely connected subproblems. | |
Ensure each subproblem is in P or provably easier than the original. | |
Output a structured breakdown. | |
🔹 Outputs: | |
A list of P-complexity subproblems. | |
A dependency graph of their relationships in ASCII format. | |
A complexity analysis report quantifying decomposition effectiveness. | |
Guidelines for Classification: | |
Problem Analysis | |
Determine if the problem is a decision, optimization, or function computation problem. | |
Identify key input/output characteristics and constraints. | |
Complexity Insights | |
Check for polynomial-time solvability via known techniques (dynamic programming, greedy methods). | |
Assess reductions to/from well-studied problems. | |
Advanced Considerations | |
Incorporate recent research (e.g., MCSP's implications for NP-completeness). | |
Evaluate parameterized complexity (FPT results) and fine-grained complexity (SETH, other conjectures). | |
Consider probabilistic or average-case complexity aspects. | |
Justification | |
Provide a concise explanation for the classification, referencing key problem features and relevant research. | |
Your Classification and Explanation: | |
''') | |
return classification | |
iface = gr.Interface( | |
fn=pvsnp, | |
inputs=gr.Textbox(label="What problem would you like to classify as P or NP?"), | |
outputs=gr.Markdown(label="Agent's response"), # Output as HTML | |
title="PolyProb", | |
description="PolyProb is an advanced AI agent that guides users through the intricate maze of computational complexity. This agent scrutinizes problem descriptions with sophisticated LLM prompts and symbolic reasoning. It classifies problems into categories such as P, NP, NP-complete, NP-hard, or beyond (e.g., PSPACE, EXPTIME), while providing clear, concise explanations of its reasoning. As part of AI Quotient’s Millennium Math Challenge, it is the first step towards solving the P vs NP problem.", | |
theme = gr.themes.Ocean(), | |
examples = ["Can you find a path that visits each node exactly once in a given graph?", "How efficiently can two nXn matrices be multiplied?", "Is there a subset of given numbers that sums to a target value?"] | |
) | |
# Launch the app | |
iface.launch() |